Обработка неоднозначности токенов в JavaCC - PullRequest
Новая
       19

Обработка неоднозначности токенов в JavaCC

0 голосов
/ 06 июня 2009

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

Рассмотрим следующую грамматику JavaCC: 

TOKEN : 
{
    ...
    < VAR : "var" > |
    < DIV : "/" > |
    < EQUALS : "=" > |
    < SEMICOLON : ";" > |
    ...
}

TOKEN :
{
    < IDENTIFIER : <IDENTIFIER_START> (<IDENTIFIER_START> | <IDENTIFIER_CHAR>)* > |
    < #IDENTIFIER_START : ( [ "$","_","A"-"Z","a"-"z" ] )> |
    < #IDENTIFIER_CHAR : ( [ "$","_","A"-"Z","a"-"z","0"-"9" ] ) >  |

    < REGEX_LITERAL : ("/" <REGEX_BODY> "/" ( <REGEX_FLAGS> )? ) > |
    < #REGEX_BODY : ( <REGEX_FIRST_CHAR> <REGEX_CHARS> ) > |
    < #REGEX_CHARS : ( <REGEX_CHAR> )* > |
    < #REGEX_FIRST_CHAR : ( ~["\r", "\n", "*", "/", "\\"] | <BACKSLASH_SEQUENCE> ) > |
    < #REGEX_CHAR : ( ~[ "\r", "\n", "/", "\\" ] | <BACKSLASH_SEQUENCE> ) > |
    < #BACKSLASH_SEQUENCE : ("\\" ~[ "\r", "\n"] ) > |
    < #REGEX_FLAGS : ( <IDENTIFIER_CHAR> )* >

}

С учетом следующего кода: 

var y = a/b/c;

Могут быть сгенерированы два разных набора токенов. Поток токенов должен быть либо: 

<VAR> <IDENTIFIER> <EQUALS> <IDENTIFIER> <DIV> <IDENTIFIER> <DIV> <SEMICOLON>

или 

<VAR> <IDENTIFIER> <EQUALS> <IDENTIFIER> <REGEX_LITERAL> <SEMICOLON>

Как я могу убедиться, что TokenManager генерирует поток токенов, который я ожидаю для этого случая?

Ответы [ 3 ]

2 голосов
/ 07 июня 2009

JavaCC всегда будет использовать самый большой доступный токен, и в противном случае его невозможно настроить. Единственный способ сделать это - добавить лексическое состояние, в случае, скажем, IGNORE_REGEX, которое исключает токен, в данном случае <REGEX_LITERAL>. Затем, когда распознается токен, за которым не может следовать <REGEX_LITERAL>, лексическое состояние должно быть переключено на IGNORE_REGEX.

С вводом: 

var y = a/b/c

Произойдет следующее:

  1. <VAR> потребляется, лексическое состояние установлено на DEFAULT
  2. <IDENTIFIER> потребляется, лексическое состояние установлено на IGNORE_REGEX
  3. <EQUALS> потребляется, лексическое состояние установлено на DEFAULT

  4. <IDENTIFIER> потребляется, лексическое состояние установлено на IGNORE_REGEX

    В этот момент в грамматике возникает неоднозначность, будет использоваться либо <DIV>, либо <REGEX_LITERAL>. Поскольку лексическое состояние равно IGNORE_REGEX и это состояние не соответствует <REGEX_LITERAL>, будет потреблено <DIV>.

  5. <DIV> потребляется, лексическое состояние установлено на DEFAULT

  6. <IDENTIFIER> потребляется, лексическое состояние установлено на IGNORE_REGEX
  7. <DIV> потребляется, лексическое состояние установлено на DEFAULT
  8. <IDENTIFIER> потребляется, лексическое состояние установлено на IGNORE_REGEX
0 голосов
/ 06 июня 2009

Поскольку JavaScript / EcmaScript делает то же самое (то есть содержит литералы регулярных выражений и оператор деления, которые выглядят так же, как в ваших примерах), вам может потребоваться изучить существующую грамматику JavaCC для изучения. Я нашел одну ссылку из этой записи в блоге , могут быть и другие.

0 голосов
/ 06 июня 2009

насколько я помню (я работал с JavaCC некоторое время назад)

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

...