Преобразование грамматики в LL (1) - PullRequest
Новая
       43

Преобразование грамматики в LL (1)

0 голосов
/ 09 апреля 2011

У меня есть эта грамматика: 

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 Ответ

1 голос
/ 09 апреля 2011

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

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

...