Выводы Yacc не могут быть распознаны

Question

Это классный проект, и я разработал 99% всех изломов, но теперь я застрял. Грамматика рассчитана на MiniJava.

У меня есть следующий ЛЕКС файл, который работает по назначению:

%{ 
#include "y.tab.h" 
%} 
delim  [ \t\n] 
ws   {delim}+ 
comment  ("/*".*"*/")|("//".*\n) 
id   [a-zA-Z]([a-zA-Z0-9_])* 
int_literal [0-9]* 
op   ("&&"|"<"|"+"|"-"|"*") 
class  "class" 
public  "public" 
static  "static" 
void  "void" 
main  "main" 
string  "String" 
extends  "extends" 
return  "return" 
boolean  "boolean" 
if   "if" 
new   "new" 
else  "else" 
while  "while" 
length  "length" 
int   "int" 
true  "true" 
false  "false" 
this  "this" 
println  "System.out.println" 
lbrace  "{" 
rbrace  "}" 
lbracket "[" 
rbracket "]" 
semicolon ";" 
lparen  "(" 
rparen  ")" 
comma  "," 
equals  "=" 
dot   "." 
exclamation "!" 

%% 

{ws}  { /* Do nothing! */ } 
{comment} { /* Do nothing! */ } 
{println} { return PRINTLN; } /* Before {period} to give this pre 
cedence */ 
{op}  { return OP;  } 
{int_literal} { return INTEGER_LITERAL; } 
{class}  { return CLASS; } 
{public} { return PUBLIC; } 
{static} { return STATIC; } 
{void}  { return VOID; } 
{main}  { return MAIN; } 
{string} { return STRING; } 
{extends} { return EXTENDS; } 
{return} { return RETURN; } 
{boolean} { return BOOLEAN; } 
{if}  { return IF; } 
{new}  { return NEW; } 
{else}  { return ELSE; } 
{while}  { return WHILE; } 
{length} { return LENGTH; } 
{int}  { return INT; } 
{true}  { return TRUE; } 
{false}  { return FALSE; } 
{this}  { return THIS; } 
{lbrace} { return LBRACE; } 
{rbrace} { return RBRACE; } 
{lbracket} { return LBRACKET; } 
{rbracket} { return RBRACKET; } 
{semicolon} { return SEMICOLON; } 
{lparen} { return LPAREN; } 
{rparen} { return RPAREN; } 
{comma}  { return COMMA; } 
{equals} { return EQUALS; } 
{dot}  { return DOT; } 
{exclamation} { return EXCLAMATION; } 
{id}  { return ID; } 
%% 

int main(void) { 
    yyparse(); 
    exit(0); 
} 

int yywrap(void) { 
    return 0; 
} 

int yyerror(void) { 
    printf("Parse error. Sorry bro.\n"); 
    exit(1); 
} 

И в YACC файла:

%token PRINTLN 
%token INTEGER_LITERAL 
%token OP 
%token CLASS 
%token PUBLIC 
%token STATIC 
%token VOID 
%token MAIN 
%token STRING 
%token EXTENDS 
%token RETURN 
%token BOOLEAN 
%token IF 
%token NEW 
%token ELSE 
%token WHILE 
%token LENGTH 
%token INT 
%token TRUE 
%token FALSE 
%token THIS 
%token LBRACE 
%token RBRACE 
%token LBRACKET 
%token RBRACKET 
%token SEMICOLON 
%token LPAREN 
%token RPAREN 
%token COMMA 
%token EQUALS 
%token DOT 
%token EXCLAMATION 
%token ID 

%% 

Program: MainClass ClassDeclList 
MainClass: CLASS ID LBRACE PUBLIC STATIC VOID MAIN LPAREN STRING LB 
RACKET RBRACKET ID RPAREN LBRACE Statement RBRACE RBRACE 
ClassDeclList: ClassDecl ClassDeclList 
    | 
ClassDecl: CLASS ID LBRACE VarDeclList MethodDeclList RBRACE 
    | CLASS ID EXTENDS ID LBRACE VarDeclList MethodDeclList RB 
RACE 
VarDeclList: VarDecl VarDeclList 
    | 
VarDecl: Type ID SEMICOLON 
MethodDeclList: MethodDecl MethodDeclList 
    | 
MethodDecl: PUBLIC Type ID LPAREN FormalList RPAREN LBRACE VarDeclLi 
st StatementList RETURN Exp SEMICOLON RBRACE 
FormalList: Type ID FormalRestList 
    | 
FormalRestList: FormalRest FormalRestList 
    | 
FormalRest: COMMA Type ID 
Type:  INT LBRACKET RBRACKET 
    | BOOLEAN 
    | INT 
    | ID 
StatementList: Statement StatementList 
    | 
Statement: LBRACE StatementList RBRACE 
    | IF LPAREN Exp RPAREN Statement ELSE Statement 
    | WHILE LPAREN Exp RPAREN Statement 
    | PRINTLN LPAREN Exp RPAREN SEMICOLON 
    | ID EQUALS Exp SEMICOLON 
    | ID LBRACKET Exp RBRACKET EQUALS Exp SEMICOLON 
Exp:  Exp OP Exp 
    | Exp LBRACKET Exp RBRACKET 
    | Exp DOT LENGTH 
    | Exp DOT ID LPAREN ExpList RPAREN 
    | INTEGER_LITERAL 
    | TRUE 
    | FALSE 
    | ID 
    | THIS 
    | NEW INT LBRACKET Exp RBRACKET 
    | NEW ID LPAREN RPAREN 
    | EXCLAMATION Exp 
    | LPAREN Exp RPAREN 
ExpList: Exp ExpRestList 
    | 
ExpRestList: ExpRest ExpRestList 
    | 
ExpRest: COMMA Exp 

%% 

деривации, которые не работают, являются следующие два:

Statement: 

| ID EQUALS Exp SEMICOLON 
| ID LBRACKET Exp RBRACKET EQUALS Exp SEMICOLON 

Если я только lex файл и получить поток токенов, маркеры соответствуют шаблону отлично. Вот пример ввода и вывода:

num1 = id1; 
num2[0] = id2; 

дает:

ID 
EQUALS 
ID 
SEMICOLON 
ID 
LBRACKET 
INTEGER_LITERAL 
RBRACKET 
EQUALS 
ID 
SEMICOLON 

То, что я не понимаю, как этот маркер потока соответствует грамматике точно, и все же YYERROR вызывается. Я пытался понять это часами, и я, наконец, сдался. Я был бы признателен за понимание того, что вызывает проблему.

Для полного примера, вы можете запустить следующий вход через анализатор:

class Minimal { 
    public static void main (String[] a) { 
     // Infinite loop 
     while (true) { 
      /* Completely useless // (embedded comment) stat 
ements */ 
      if ((!false && true)) { 
       if ((new Maximal().calculateValue(id1, i 
d2) * 2) < 5) { 
        System.out.println(new int[11].l 
ength < 10); 
       } 
       else { System.out.println(0); } 
      } 
      else { System.out.println(false); } 
     } 
    } 
} 

class Maximal { 

    public int calculateValue(int[] id1, int id2) { 
     int[] num1; int num2; 
     num1 = id1; 
     num2[0] = id2; 
     return (num1[0] * num2) - (num1[0] + num2); 
    } 
} 

Он должен разобрать правильно, но расцепления на num1 = id1; и num2[0] = id2;.

PS - Я знаю, что это семантически неправильно MiniJava, но синтаксически, это должно быть хорошо :)

Answer 1

Там нет ничего плохого с определениями Statement. Причина, по которой они вызывают ошибку, заключается в том, что они начинаются с ID.

Начнем с того, когда зубры обрабатывает введенные данные, он сообщает:

minijava.y: conflicts: 8 shift/reduce 

конфликтов сдвиг/свёртка не всегда проблема, но вы не можете просто игнорировать их. Вы должны знать, что их вызывает, и будет ли поведение по умолчанию правильным или нет. (Поведение по умолчанию предпочитать сдвиг по сокращению.)

Шестеро сдвиг/свёртка конфликты исходят из того, что:

Exp: Exp OP Exp 

, который по своей природе неоднозначно. Вам нужно будет исправить это, используя фактические операторы вместо OP и вставляя правила приоритета (или конкретные производственные задания). Это не имеет ничего общего с непосредственной проблемой, и поскольку на данный момент нет (важно), будет ли первый Exp или второй приоритет, разрешение по умолчанию будет прекрасным.

Другие из них приходят из следующей продукции:

VarDeclList: VarDecl VarDeclList 
      | %empty 

Здесь VarDecl может начинаться с ID (в случае класса, используемого в качестве типа).

VarDeclList в настоящее время производятся из MethodDecl:

MethodDecl: ... VarDeclList StatementList ... 

Теперь, скажем, мы разбор входа; мы просто разобраны:

int num2; 

и мы смотрим на следующий знак, который num1 (от num1 = id1). int num2;, конечно, VarDecl, поэтому он будет соответствовать VarDecl в

VarDeclList: VarDecl VarDeclList 

В этом контексте, VarDeclList может быть пустыми, или он может начать с другим заявлением. Если он пуст, нам нужно немедленно его сократить (потому что у нас не будет другого шанса: не-терминалы должны быть сокращены не позднее, чем когда их правые части будут завершены). Если он не пуст, мы можем просто перенести первый токен. Но мы должны принять это решение на основе текущего токена, который является ID.

К сожалению, это нам не поможет. И VarDeclList, и StatementList могут начинаться с ID, поэтому возможны и сокращение, и сдвиг. Следовательно, bison сдвиги.

Теперь предположим, что VarDeclList использует левую рекурсию вместо правого рекурсии. (Левая рекурсия почти всегда лучше в LR-грамматик.):

VarDeclList: VarDeclList VarDecl 
      | %empty 

Теперь, когда мы достигаем конец VarDecl, у нас есть только один вариант: уменьшить VarDeclList. И тогда мы будем в следующем состоянии:

MethodDecl: ... VarDeclList · StatementList 
VarDeclList: VarDeclList · VarDecl 

Теперь мы видим ID lookhead, и мы не знаем, начинается ли это StatementList или VarDecl. Но это неважно, потому что нам не нужно уменьшать ни один из этих нетерминалов; мы можем дождаться, чтобы увидеть, что будет дальше, прежде чем совершать то или другое.

Обратите внимание, что в этом случае существует небольшая смысловая разница между лево-и право-рекурсией. Очевидно, что синтаксические деревья разные:

  VDL       VDL 
     / \      / \ 
     VDL Decl     Decl VDL 
    / \       / \ 
    VDL Decl       Decl VDL 
    |          | 
    λ          λ 

Однако на практике наиболее вероятные действия будут:

VarDeclList: %empty    { $$ = newVarDeclList(); } 
      | VarDeclList VarDecl { $$ = $1; appendVarDecl($$, $2); } 

, который работает просто отлично.

---

Кстати:

1) В то время как прогибается позволяет использовать определения для того, чтобы упростить регулярные выражения, он не требует, чтобы использовать их, и нигде не написано, что (к моему знанию), что лучше использовать определения. Я использую определения экономно, обычно только тогда, когда я собираюсь написать два регулярных выражения с одним и тем же компонентом, или иногда, когда регулярное выражение действительно сложно, и я хочу разбить его на части. Тем не менее, нет абсолютно никакой необходимости загромождать свой файл гибкий с:

begin   "begin" 
... 
%% 
... 
{begin}   { return BEGIN; } 

, а не проще и более читаемым

"begin"   { return BEGIN; } 

2) В том же ключе, bison услужливо позволяет писать одно- символьные жетоны как одноцилиндровые литералы: '('. Это имеет ряд преимуществ, начиная с того, что он обеспечивает более читаемый вид грамматики. Кроме того, вам не нужно объявлять эти жетоны или придумывать им хорошее имя. Более того, поскольку значение токена является самим символом, ваш файл flex также может быть упрощен. Вместо

"+"  { return PLUS; } 
"-"  { return MINUS; } 
"("  { return LPAREN; } 
... 

вы можете просто написать:

[-+*/(){}[\]!] { return yytext[0]; } 

На самом деле, я обычно рекомендую даже не использовать это; просто использовать кетчуп все гибкое правило в конце:

.    { return yytext[0]; } 

Это будет проходить иначе несовпадающие символы как односимвольные токены для Bison; если токен не известен бизону, он выдаст синтаксическую ошибку. Таким образом, вся обработка ошибок централизована в бизоне, а не разделяется между двумя файлами, и вы сохраняете много ввода (и тот, кто читает ваш код, сохраняет много чтения.)

3) Это не обязательно поставить "System.out.println" до ".". Их никогда нельзя путать, потому что они не начинаются с одного и того же персонажа. Единственный порядок времени имеет значение, если два шаблона будут максимально соответствовать одной и той же строке в одной и той же точке (поэтому шаблон ID должен появиться после всех отдельных ключевых слов).