Yacc / Lexer: как это работает на самом деле? - PullRequest
Новая
       5

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

1 голос
/ 16 февраля 2012

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

Если у меня есть очень простая программа, как бы я проанализировал первые строки этого тестового языка программирования?Предположим, что «программа» - это определенное значение в lex, а также «is», «var», «begin», «+», «print», «;», «,» и «end».

Как записать файл 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"); }
}

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

1 Ответ

1 голос
/ 16 февраля 2012

Вам потребуется создать как файл lex, так и файл yacc.В файле lex вы определяете отдельные токены для каждого типа токенов, которые содержатся в вашей грамматике.Затем вы строите грамматику в форме BNF, подходящей для 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 здесь

...