Converting a grammar to LL(1)
I have this grammar:
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
I partially wrote a recursive descent parser:
void Parser::ntProgram()
{
ntExprList();
}
vo开发者_如何学编程id 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))
{
}
}
But I don't know what to do in some parts, for example the way that an expr can be an lvalue, whose first item could be an expr.
In order to be able to parse the expr rule, you have to eliminate left recursion first. This is well explained on Wikipedia:
http://en.wikipedia.org/wiki/Left_recursion
精彩评论