Преобразование грамматики в 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.


person mtk358    schedule 08.04.2011    source источник


Ответы (1)


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

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

person ollb    schedule 08.04.2011
comment
Вот несколько ссылок на левую рекурсию на SO: stackoverflow.com/questions/3036021/ stackoverflow.com/questions/5425977/ - person Andy; 09.04.2011
comment
Я видел руководства по удалению непосредственной левой рекурсии только в таких вещах, как математические выражения, где с одной стороны есть более ограниченная форма выражения. Но в правиле вызова функции первое выражение действительно должно соответствовать любому виду выражения, даже вызовам других функций, циклам while и т. д. - person mtk358; 09.04.2011