рукописный анализатор сверху вниз

Question

Я наткнулся на этот ответ для написания анализатора сверху вниз: Is there an alternative for flex/bison that is usable on 8-bit embedded systems?, но я смущен несколькими пунктами.

Скажем, у меня есть эта грамматика:

Expr = Id | Id '(' Expr ')' 
Stmt = Id '=' Expr | Expr 

я не уверен, если это строго необходимо, но я думаю, мы можем слева фактор грамматику:

Expr = Id ExprRest 
ExprRest = ϵ | '(' Expr ')' 
Stmt = Id '=' Expr ';' | Expr ';' 

Как именно я хотел бы написать код что правильно обрабатывает foo(x); как Stmt? Если мы напишем код Stmt синтаксического анализа, как:

func ParseStmt() { 
    if ParseId() { 
    return ParseTerminal('=') && ParseExpr() && ParseTerminal(';'); 
    } else { 
    return ParseExpr() && ParseTerminal(';'); 
    } 
} 

Увидим Idfoo, предположим, что мы в первом случае, а затем не потому, что мы не в состоянии найти = следующие foo.

Является ли эта грамматика не LL (1)?

Answer 1

Эта грамматика не является LL(1), потому что грамматика LL(1) должна быть в состоянии определить, какое производство нужно развернуть, учитывая только пар синтаксического анализа и токен поиска. С пустым стеком разбора вы не можете определить, какую из двух Stmt производств использовать с использованием токена Id. Вы можете левого фактора, но это раздражает.

Исполняемые файлы, созданные bison, хотя они занимают много строк C, на самом деле довольно компактны. Ваша грамматика, составленная бизоном, произвела 1559 строк C, но скомпилирована в объектный файл 4K, из которых (я считаю) лишь немногим более 1K соответствует фактическому коду и данным. (Конечно, это без действий.)

Если вы действительно хотите обработать парсер для выражения грамматики выражения, я бы предложил использовать либо снизу вверх «алгоритм Shunting Yard», либо «сверху вниз», Pratt parser '(оба из которых легко доступны для поиска в Google), которые лучше обрабатывают такие вещи, как приоритет оператора, чем строгая грамматика LL. Но вы вполне можете обнаружить, что грамматика, созданная бизоном, сопоставима по размеру и скорости, а также улучшена читаемость и удобство обслуживания. (Или, может быть, нет. Вкусы отличаются.)

Answer 2

Ваша проблема в том, что ID (xxx) может отображаться как в контексте операторов, так и в выражениях.

Как говорится в другом ответе, вы должны учитывать больше. Это не так сложно. Написать грамматику, как это:

Stmt = Id ('=' Expr ';' | 
      RestOfExpression); 

RestOfExpression = '(' Expr ')' | 
        ϵ); 
Expr = Id RestOfExpression; 

Код должен быть очевиден.