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

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

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. Я получаю сообщение об ошибке, указывающее на то, что идентификатор () недоступен. Это правило условного производства:

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

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


parsing compiler-construction javacc unreachable-statement
person Conor Murphy    schedule 11.12.2013    source источник

Ответы (1)


arrow_upward
6
arrow_downward

У вас есть

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) не будет выбрана. Так что в любом случае альтернатива (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

ваш парсер примет, например, «ПОКА a + b DO a: = b». Во многих языках это решается проверкой типов; Java делает это так. В других языках с этим справляются, разрешая все виды вещей как условия; LISP делает это.

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

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

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

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

Теперь грамматика не LL (1) (это даже не однозначно). Таким образом, JavaCC выдаст некоторые предупреждения о конфликте выбора. Но на самом деле он будет разбирать, например. "NOT a LT b" как "NOT (a 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» как условие, даже если оно числовое. Если вы знаете об этом и спроектируете остальную часть компилятора так, чтобы все по-прежнему работало, вреда не будет.

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

person Theodore Norvell    schedule 11.12.2013