Yacc/Lexer: как это работает на самом деле?

Я пытался сидеть здесь и читать руководства о том, как YACC работает с файлом lex, однако я не уверен, что смогу понять это. Я понимаю, что это для чтения фактического входного файла и определения того, имеют ли такие функции, как сложение или вычитание, правильный формат, но как это работает? Я понимаю, как работают файлы Lex, и создал файл, который возвращает определенные переменные на основе того, что встречается в файле.

Если у меня есть очень простая программа, как мне проанализировать первые строки этого тестового языка программирования. Предположим, что «программа» является определенным значением в lex, а также «есть», «вар», «начало», «+», «печать», «;», «,» и «конец».

Как должен быть написан файл yacc, чтобы можно было прочитать первые несколько строк?

Тестовый файл:

program xyz is 
var a, b, c
begin
  a = 2;
  b = 3;
  c = a + b;
  print c
end

Yaccer.y

%token EOFNUM       0
%token SEMINUM      1
%token LPARENNUM    2
%token RPARENNUM    3
%token ICONSTNUM    4
%token BEGINNUM     5
%token PROGRAMNUM   6
%token MINUSNUM     7
%token TIMESNUM     8
%token VARNUM       9
%token COMMANUM     10
%token IDNUM        11
%token ENDNUM       12
%token ISNUM        13
%token PLUSNUM      14
%token DIVNUM       15
%token PRINTNUM     16
%token EQUALNUM     17

%left '+' '-'
%left '*' '/'

%%


%%

#include "lex.yy.c"
#include <stdio.h>

yyerror(str)
char *str;
{   printf("yyerror: %s at line %d\n", str, yyline); }

main () {
    if (!yyparse()) { printf("accept\n");}
    else { printf("reject\n"); }
}

Я знаю, что для уравнений должны быть определены некоторые %types, однако я не уверен, как использовать типы вместе с объявлениями %left, или даже если это правильно. Я также смущен тем, как я анализирую первую строку.


yacc lex
person Alex Muller    schedule 16.02.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вам нужно будет создать как файл lex, так и файл yacc. В файле lex вы определяете отдельные токены для каждого типа токенов, которые содержит ваша грамматика. Затем вы строите грамматику в форме БНФ, подходящую для yacc. Для вашего простого ввода это выглядит примерно так. Я предполагаю, что это опечатка, что оператор print не имеет ; после него, и эта грамматика требует точки с запятой.

%token IDENTIFIER
%token PROGRAM
%token BEGIN
%token END
%token IS
%token VAR
%token PRINT
%token NUMBER

program
statementlist
statement
printstatement
assignstatement 
expression

%%

program : PROGRAM IDENTIFIER IS VAR variables BEGIN statementlist END;

variables : IDENTIFIER | variables ',' IDENTIFIER;

statementlist : statement | statementlist statement;

statement : assignstatement | printstatement;

printstatement : PRINT IDENTIFIER ';';

assignstatement : IDENTIFIER '=' expression ';';

expression : value | expression '+' value;

value : NUMBER | IDENTIFIER;

%%

%left и %right являются модификаторами ассоциативности и в вашем случае не нужны. Они были бы необходимы, если бы вы поддерживали -, используя тот же приоритет, что и +. Ну, технически это не очень нужно, но они облегчают понимание грамматики.

Yacc не прост для понимания, и я рекомендую учебник по этому вопросу. Правила очень быстро приобретают рекурсивный характер и нужно иметь определенный настрой при работе с ними. Легче строить грамматику постепенно, начиная с оператора высшего порядка. Сделайте синтаксический анализатор, который просто распознает начало программы, а затем работает с функциями по ходу дела.

Хорошим инструментом для тестирования и проверки грамматики является генератор синтаксического анализатора javascript, который можно найти здесь.

person Dervall    schedule 16.02.2012