Javacc Недоступное заявление

Question

В моей грамматике есть производственные правила для выражений и фрагментов, которые изначально содержали косвенную левую рекурсию. Это правила после того, как я удалил из них рекурсию.

String expression() #Expression : {String number; Token t;}
{
    number = fragment()
    (
        (t = <Mult_Sign> number = fragment())
    )
    {return number;}
}

String fragment() #void : {String t;}
{
    t = identifier() {return t;}
    | t = number() {return t;}
    | (<PLUS> | <MINUS> ) fragment()
    | <LBR> expression() <RBR>
}

Эти производственные правила используются при попытке разобрать условие в грамматике. Однако порядок правил производства также имеет его, поэтому принимается только выражение. Тем не менее, он должен принять что-то вроде while (x <= 10). Если у меня есть правила производства в обратном порядке, как первоначально указано в грамматике. Когда я пытаюсь скомпилировать файл Java, используя Javac. Я получаю сообщение об ошибке, в котором говорится, что identifier() - недостижимое утверждение. Это правило производства условия:

void condition() #void : {Token t;}
{
    <NOT> expression()
    | expression (<EQUALS>|<NOTEQUALS>|<LT>|<GT>|<LTE>|<GTE>|<AND>|<OR>) expression()
    | identifier()
}

Если кто-то может помочь мне сказать, почему эта проблема возникает, это было бы очень полезно.

Answer 1

У тебя есть

void condition() #void : {Token t;}
{
/*a*/     <NOT> expression()
/*b*/     | expression (<EQUALS>|<NOTEQUALS>|<LT>|<GT>|<LTE>|<GTE>|<AND>|<OR>) expression()
/*c*/     | identifier()
}

Если синтаксический анализатор ищет условие, он попытается сделать выбор между тремя альтернативами на основе следующего токена ввода. Если этот токен является идентификатором, возникает проблема, так как альтернатива (b) или альтернатива (c) могут работать. Столкнувшись с конфликтом выбора, JavaCC предпочитает первый, поэтому будет выбран вариант (b). И если следующий токен не является идентификатором, тогда альтернатива (c) не будет выбрана. Так что в любом случае альтернатива (с) не будет достигнута.

---

Это твоя проблема. Что с этим делать? Вот обычное решение.

Если вы хотите разрешить дополнительные операторы в выражениях, сделайте больше нетерминалов, представляющих больше уровней приоритета. Например

condition --> expression
expression --> disjunct (OR expression)?
disjunct --> conjunct (AND disjunct)?
conjunct --> comparand ((EQ|NEQ|LT|GT|LE|GE) comparand)?
comparand --> term ((PLUS|MINUS) term)*
term --> fragment ((TIMES | DIVIDE) fragment)*
fragment --> identifier | number | LBR expression RBR | (PLUS|MINUS|NOT) fragment

Эта грамматика примет все, что вы хотите и, возможно, больше. Например, если у вас есть

statement --> WHILE condition DO statement

Ваш парсер примет, например, "WHILE a+b DO a:=b". Во многих языках об этом заботится проверка типов; Java делает это таким образом. На других языках это разрешается путем разрешения всех видов вещей как условий; LISP делает это.

---

Примечание о приоритете НЕ

Большинство языков рассматривают приоритет НЕ так высоко, как во второй части этого ответа. Это имеет хороший эффект устранения всех предупреждений выбора, поскольку грамматика - LL(1).

Однако, если вы хотите, чтобы унарные операторы имели более низкий приоритет, вас ничто не остановит, если вы используете JavaCC. Например, вы можете изменить фрагмент на

fragment --> identifier | number | LBR expression RBR | (PLUS|MINUS) fragment | NOT conjunct

Теперь грамматика не является LL(1) (это даже не однозначно). Так что JavaCC выдаст несколько предупреждений о конфликте выбора. Но он на самом деле будет анализировать, например, "НЕ a LT b" как "НЕ (LT b)"

---

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

Начните с такой грамматики. (Это по сути ваша идея с большим вниманием к уровням приоритета.)

condition --> disjunct (OR condition)?
disjunct --> conjunct (AND disjunct)?
conjunct --> expression (EQ|NEQ|LT|GT|LE|GE) expression
           | LBR condition RBR
           | NOT conjunct
           | identifier

expression --> term ((PLUS|MINUS) term)*
term --> fragment ((TIMES | DIVIDE) fragment)*
fragment --> identifier | number | LBR expression RBR | (PLUS|MINUS) fragment

Это однозначная грамматика для условий. Однако он имеет конфликт выбора в соединении, когда следующий токен является идентификатором или LBR. Чтобы разрешить этот конфликт выбора, вы смотрите в будущее на оператор сравнения, используя

void conjunct() : { } {
    LOOKAHEAD( expression() (<EQ>|<NEQ>|<LT>|<GT>|<LE>|<GE>) )
    expression() (<EQ>|<NEQ>|<LT>|<GT>|<LE>|<GE>) expression()
|   LBR condition() RBR
|   NOT conjunct()
|   identifier() {

Так почему (почти) ни один язык программирования не делает это таким образом? Большинство языков имеют переменные логического типа и поэтому, как и вы, допускают идентификаторы в качестве условий. Таким образом, вы все равно должны выполнить проверку типа, чтобы исключить "WHILE i DO ...", где "i" не имеет логического типа. Кроме того, что вы должны использовать для синтаксиса присваивания? Тебе нужно

statement --> identifier := (expression | condition) | ...

Даже синтаксический просмотр не скажет вам, какой выбор является правильным для "x:= y". Это неоднозначная грамматика.

Если любой из вариантов приемлем в случаях, когда оба варианта разбираются, то здесь вы также используете синтаксический просмотр.

void statement() : {} {
    identifier <BECOMES> (LOOKAHEAD(condition()) condition()) | expression())
| ...
}

Это будет анализировать "y" в "x: = y" как условие, даже если оно числовое. Если вы знаете об этом и спроектируете остальную часть компилятора так, чтобы все по-прежнему работало, никакого вреда не будет.

Еще одним недостатком этого подхода является то, что в настоящее время синтаксический анализ в теории является квадратичным временем. Я не думаю, что это серьезная проблема.