2011-04-08 10 views
0

У меня есть эта грамматика:Преобразование грамматики для LL (1)

program ::= expr_list 

expr_list ::= {LF} [expr {LF {LF} expr}] {LF} 

lvalue ::= [expr DOT] NAME 

call_param ::= [[NAME COLON] expr {COMMA [NAME COLON] expr}] 

func_param ::= [NAME [COLON expr] {COMMA NAME [COLON expr]}] 

expr ::= lvalue 
     | lvalue ASSIGN expr 
     | expr OPAREN call_param CPAREN 
     | FUNC func_param LF expr_list END 
     | IF expr LF expr_list {ELSEIF expr LF expr_list} [ELSE expr_list] ENDIF 
     | WHILE expr LF expr_list LOOP 
     | DO expr_list LOOP WHILE expr LF 
     | INTEGER 

Я частично написал рекурсивный спуск парсер:

void Parser::ntProgram() 
{ 
    ntExprList(); 
} 

void Parser::ntExprList() 
{ 
    // ??? 
} 

void Parser::ntLvalue() 
{ 
    // ??? 
} 

void Parser::ntCallParam() 
{ 
    // ??? 
} 

void Parser::ntFuncParam() 
{ 
    if (accept(Lexer::NameTok)) { 
     if (accept(Lexer::ColonTok)) { 
      ntExpr(); 
     } 
    } 
    while (accept(Lexer::CommaTok)) { 
     expect(Lexer::NameTok); 
     if (accept(Lexer::ColonTok)) { 
      ntExpr(); 
     } 
    } 
} 

void Parser::ntExpr() 
{ 
    if (accept(Lexer::FuncTok)) 
    { 
     ntFuncParam(); 
     expect(Lexer::LfTok); 
     ntExprList(); 
     expect(Lexer::EndTok); 
    } 
    else if (accept(Lexer::WhileTok)) 
    { 
     ntExpr(); 
     expect(Lexer::LfTok); 
     ntExprList(); 
     expect(Lexer::LoopTok); 
    } 
    else if (accept(Lexer::DoTok)) 
    { 
     ntExprList(); 
     expect(Lexer::WhileTok); 
     expect(Lexer::LoopTok); 
     ntExpr(); 
     expect(Lexer::LfTok); 
    } 
    else if (accept(Lexer::IfTok)) 
    { 
     ntExpr(); 
     expect(Lexer::LfTok); 
     ntExprList(); 
     while (accept(Lexer::ElseifTok)) 
     { 
      ntExpr(); 
      expect(Lexer::LfTok); 
      ntExprList(); 
     } 
     if (accept(Lexer::ElseTok)) 
     { 
      ntExprList(); 
     } 
     expect(Lexer::EndifTok); 
    } 
    else if (accept(Lexer::IntegerTok)) 
    { 
    } 
} 

Но я не знаю, что делать в некоторых частях , например, способ, которым expr может быть lvalue, чей первый элемент может быть expr.

ответ

1

Для того, чтобы проанализировать правило expr, сначала необходимо устранить левую рекурсию. Это хорошо объясняется в Википедии:

http://en.wikipedia.org/wiki/Left_recursion

+0

Вот некоторые левые ссылки рекурсии на SO: http://stackoverflow.com/questions/3036021/how-to-implement-a-left-recursion-eliminator HTTP : //stackoverflow.com/questions/5425977/how-to-remove-left-recursive-in-this-antlr-grammer – Andy

+0

Я видел только руководства по удалению немедленной левой рекурсии в таких вещах, как математические выражения, где есть более ограниченная форма выражения с одной стороны. Но в правиле вызова функции первый «expr» действительно должен соответствовать любому выражению, даже другим вызовам функций, а также петлям и т. Д. – mtk358

 Смежные вопросы

  • Нет связанных вопросов^_^