Напишите синтаксический анализ с рекурсивным спуском для разбора epsilon (ε) в Java

Question

Например,

EBNF

A :: = B c;

B :: = T1 |T2 |ε

T1 :: = a

T2 :: = b

parseA()
{
switch(currentToken.kind){
case Token.a :
    parseT1();
case Token.b :
    parseT2();
break;

case <epsilon> :

break;
default:
    // report error
break;
}
}

Как написать синтаксический анализатор парсинг (набор пустой строки)Java?

Answer 1

Будь то Java или любой другой язык, дело в том, что у вас есть поток токенов.Вы не «получаете» токен и не решаете, что делать.Скорее вы «смотрите» на следующий токен, и если вы можете использовать его, вы «принимаете» его.

Видите разницу?

Не «получайте», а затем «решайте».
Сделайте «посмотрите и решите», а затем «примите».
Это основа концепции «предвидения».

Итак, ParseA вызывает ParseB.

Parse Bсмотрит на следующий токен в потоке.
Если это "a", он принимает его и возвращает.
Если это "b", он принимает его и возвращает.
В противном случае он просто возвращается в ParseA (безпринимая что-либо).

Затем ParseA смотрит на следующий токен.
Если это "c", он принимает его и возвращает.
В противном случае он не работает.

Имеет смысл?

Чтобы сделать это, вы должны добавить маркер часового в конец потока, который никогда не будет принят.В конце это должен быть единственный токен, оставшийся в потоке.Если нет, у вас есть синтаксическая ошибка, состоящая из лишнего мусора в конце.

Answer 2

epsilon - это просто маркер «здесь разрешена пустая строка», поэтому вам не нужно ничего анализировать;спуск закончен.Кажется маловероятным, что у вас на самом деле был бы токен для этого;вам нужно определить, нет ли доступного токена или можно ли использовать следующий токен в другом производстве.

Например, вы можете получить ввод c.Вы должны понимать, что это соответствует производству A ::= B c;, потому что B может быть уменьшено до epsilon - токена epsilon нет, вам просто нужно понять, что правило B там необязательно, и в этом случаенужно пропустить, чтобы уменьшить c до A

Answer 3

На самом деле, это немного упрощенно, чтобы иметь смысл как синтаксический анализатор. Все это можно записать в виде простого регулярного выражения: «[ab]? C». Если вы действительно настаиваете на написании парсера, код может выглядеть примерно так:

Boolean parseA() { 
    // an A is a B followed by a `c`:
    return parseB() && (get_token() == Token.c);
}

Boolean parseB  {
    // Get a token. 
    //     If it's an `a` or a `b`, consume it. 
    //     Otherwise, throw it back (match null string by consuming nothing).
    // Either way, return true (successful match).
    //
    token current_token = get_token();
    if (token != Token.a && token != Token.b)
        push_back(current_token);
    return true;
}

Изменить (в ответ на комментарий к другому ответу): Нет, когда вы соответствуете B, вы должны , а не искать Token.c. Что касается B, есть три варианта: сопоставить «a», сопоставить «b» или вообще ничего не сопоставить. Затем часть, которая анализирует A, проверяет наличие B, а затем Token.c.

Например, если вам нужно изменить грамматику на что-то вроде:

A :: = B C

B :: = a | б | ε

C :: = c | д

Поскольку «B» по-прежнему имеет то же определение, вы должны не изменять его только потому, что некоторые другие определения изменены. Аналогично, вы можете добавить к грамматике, чтобы разрешить (например) произвольную строку B, за которой следует C.

Answer 4

Вы 'разбираете' эпсилон, когда видите что-либо в наборе FOLLOW текущего нетерминала. Так как FOLLOW (B) = {'c'}, вы используете case Token.c: в переключателе в parseB для него