开发者

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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜