Как я могу реализовать правило синтаксического анализа в ANTLR, который объединяет два узла в один? - PullRequest
Новая
       1

Как я могу реализовать правило синтаксического анализа в ANTLR, который объединяет два узла в один?

2 голосов
/ 28 ноября 2011

Второй вариант ((1-9) (0-9)) следующего правила синтаксического анализатора приводит к двум узлам в дереве абстрактного синтаксиса. 

oneToHundred
  : ('1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')
  | ('1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')
  | '100'
  ;

( боковой узел:"Лексирование" чисел в Digit-Tokens для меня неприменимо, поскольку иногда поддиапазон 0-9, такой как 2-4, может представлять sth. сильно отличается от цифры (на которую я не могу повлиять). )

Так что для 15 я получаю два узла один и пять вместо пятнадцати, но я бы хотел получить это как одно число, представленное одним узлом.

Я не могу сделать это с лексером на уровне токена, поскольку зависит от контекста например. 15 может означать две очень разные вещи: «один символ и пять символов» (которые определенно должны быть двумя узлами) или «пятнадцать» и в соответствии с этим постом контекстно-зависимая следует оставить парсеру.

(Изменить для уточнения:)

Пример чувствительности к контексту:

Входные данные должны быть разделены / разделены точками с запятой 

Input:
11;2102;34%;P11o

this would be split into four parts and 
11 - would not be a number but one '1'-symbol and another '1'-symbol
2102 - would not be a number but: '2'-symbol '1'-symbol '0'-symbol '2'-symbol 
34% - now here 34 would be the number thirtyfour
P11o: 'P'-symbol '1'-symbol '1'-symbol 'o'-symbol

Из этих четырех блоков 34% будут распознаваться как процентные блоки по правилу синтаксического анализатора, а остальные как символьные блоки. Таким образом, AST должен выглядеть примерно так: 

SYMBOL
  1
  1
SYMBOL
  2
  1
  0
  2
PERCENT
  34
SYMBOL
  P
  1
  1
  o

Цель - C #: 

options {
  language=CSharp3;
  output=AST;
}

Я Antlr-noob, так есть ли хороший способ объединить эти два узла с синтаксическим анализатором или мне лучше добавить воображаемый токен и объединить две цифры "вручную" в C # после анализа?

1 Ответ

1 голос
/ 28 ноября 2011

Правило вашего парсера: 

oneToHundred
 : ('1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')
 | ('1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')
 | '100'
 ;

неявно создает следующие токены за кулисами: 

D_1_9 : ('1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9');
D_0_9 : ('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9');
D_100 : '100';

(не с этими именами правил, но содержимое, которому они соответствуют , создано )

Таким образом, если ваш лексер получит входные данные "11", будут созданы два токена D_1_9 и альтернатива 2 nd из правила oneToHundred не сможет быть сопоставлена ​​(эта альтернатива нужны два жетона: D_1_9 D_0_9).

Вы должны понимать, что лексер работает независимо от парсера. Неважно, какой токен синтаксический анализатор «запрашивает» у лексера: у лексера есть свои собственные приоритеты, в результате чего '1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9' никогда не будет соответствовать правилу D_0_9 (потому что он приходит после правило D_1_9.

EDIT

Давайте назовем ваш ввод, 11;2102;34%;P11o, четырьмя единицами, состоящими из atoms (где atom - буква или цифра), возможно, оканчивающихся на '%': 

unit
  :  atoms '%'?
  ;

Если оно заканчивается '%', вы просто используете правило перезаписи для создания дерева с PERCENT в качестве корня, в противном случае просто создайте дерево с SYMBOL в качестве корня: 

unit
  :  (atoms -> ^(/* SYMBOL */)) ('%' -> ^( /* PERCENT */))?
  ;

Рабочая демоверсия: 

grammar T;

options {
  output=AST;
  ASTLabelType=CommonTree;
}

tokens {
  ROOT;
  SYMBOL;
  PERCENT;
  NUMBER;
}

parse
  :  unit (';' unit)* EOF -> ^(ROOT unit+)
  ;

unit
  :  (atoms -> ^(SYMBOL atoms)) 
     ('%' -> ^(PERCENT {new CommonTree(new CommonToken(NUMBER, $atoms.text))}))?
  ;

atoms
  :  atom+
  ;

atom
  :  Letter
  |  Digit
  ;

Digit  : '0'..'9';
Letter : 'a'..'z' | 'A'..'Z';

Вы можете протестировать анализатор, используя следующий класс: 

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
  public static void main(String[] args) throws Exception {
    TLexer lexer = new TLexer(new ANTLRStringStream("11;2102;34%;P11o"));
    TParser parser = new TParser(new CommonTokenStream(lexer));
    CommonTree tree = (CommonTree)parser.parse().getTree();
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT(tree);
    System.out.println(st);
  }
}

, который будет выдавать DOT-вывод, соответствующий следующему AST:

enter image description here

На изображении выше все листья имеют тип Letter или Digit, кроме "34", тип которого NUMBER.

...