По Antlr подскажите... - Средства разработки

Пишу парсер некоего самопального конфига. В конфиге среди прочего встречаются в вещи типа filter = "тут какая-то строка". Соответственно в грамматике это выглядит примерно так id '=' quotedString.
Но внезапно возникла необходимость включить в конфиг (и соответственно — парсить) некие простейшие выражения типа таких QQ > 1, AA < 10, ZZ = "это строка". Нарисовал правила типа такого (пишу по памяти):
Int: (0..9)+;
Operation: '='|'<'|'>'|''<=|'>='|'<>';
expr: token Operation (Int | quotedString) ;

Ругается на '='. Если для обозначения операции равенства использовать '==', то всё работает.
Лексер и парсер описываются в одном файле грамматики.

Вопрос первый: можно ли как-то использовать '=', а не '=='. Можно конечно парсером выдирать всё выражения и разбирать далее руками, но не хочется.

Вопрос второй на понимание (может смешной, но я в грамматиках лох): описанное выше проиходит от того, что ANTLR описывает контекстно-свободные грамматики? Т.е. если символ/токен где-то используется для одного действия (у меня для обозначения присвоения), то в другом значении его использовать нельзя. А была-бы контекстно связанная, то значение символа/токена могло бы зависть бы от контекста, и тогда бы разборе выражения был бы (можно было бы сделать) другой контекс со своим значением символа '='. Так?

Здравствуйте, Кондраций, Вы писали:

К>Вопрос первый: можно ли как-то использовать '=', а не '=='. Можно конечно парсером выдирать всё выражения и разбирать далее руками, но не хочется.
К>Вопрос второй на понимание (может смешной, но я в грамматиках лох): описанное выше проиходит от того, что ANTLR описывает контекстно-свободные грамматики?

Начну со второго вопроса. Описанное выше просиходит из-за того, что ANTLR не разбирает произвольные контекстные грамматики. Он разбирает LR(1) (или LALR, не помню уже) грамматики, которые являются подмножеством контекстно-свободных.

Вообще,контекстно-свободная грамматика не про возможность использования символов ('=', '==', 'var' — и т.п. — терминалы называются). Она про возможность использования правил из самой грамматики. Т.е. допустим мы пишем код. У нас есть правило

expr: int
expr: '(' expr '+' expr ')'
if: 'if' expr 'then' statement
assign: var '=' expr

В контекстно-свободной грамматике всегда можно написать '(1 + 2)' там, где по грамматике положен expr. Т.е. можно использовать сумму как в if, так и в assign. А вот в контекстно-зависимой грамматике это уже не правда. Например, можно сказать, что сложение можно использовать только после знака присваивания (но не в операторе if). При этом и в присваивании, и в if все равно будет "expr". Такую контекстно-зависимую грамматику можно выразить как

expr: int
var '=' expr: var '=' '(' expr '+' expr ')'
if: 'if' expr 'then' statement
assign: var '=' expr

Теперь к первому вопросу. ANTLR не разбирает произвольные грамматики. Он разбирает только грамматики определенного вида по строго определенному алгоритму. Детальное описание можно найти в книгах и конспектах лекций по компиляторам. Если на пальцах, он хранит "стек" состояний (начальные части выражений). И может заменять только "группу символов на вершине стека" на определенный литерал в левой части. На примере выражения выше (в середине выражения, первые шаги не показаны, стек растет слева на право):

var['x'] '=' '(' expr['3'] '+' '1'
// Ух ты, 1 - это же expr
var['x'] '=' '(' expr['3'] '+' expr['1']
// Ничего не понятно - нужно взять следующий токен
var['x'] '=' '(' expr['3'] '+' expr['1'] ')'
// О! Оно оказывается на expr кончается, надо заменить
var['x'] '=' expr['(3 + 3)']
// А это - assign!
assign['x = (3 + 3)']

Но так происходит только в простом случае. Для более сложной грамматики по текущему стеку не всегда можно определить, во что сворачивается (по какому правилу заменяется) терминал. Например:

variableName: string
functionName: string
call: functionName '(' ')'
assign: variableName '=' variableName

В этом случае выражение 'x()' все еще можно разобрать на стеке, если посмотреть на следующий символ:

'x'
// Строка!
string['x']
// Хм... Не понятно пока, функция это или переменная.
// Что там дальше? '('? Значит, это функция!
functionName['x']
// Пока все, берем следующий токен ...

А вот в более сложной грамматике такое может не получиться сделать.

id: string
token: string
filterDef: id '=' int
expr: token '=' string

Вот здесь при разборе выражения нельзя понять, что такое 'x' в выражении 'x = ...'. Это id (и идет определение фильтра) или token (и идет выражение)?

Т.е. парсер должен работать примерно так:

'x'
// Строка!
string['x']
// Хм... не понятно. id? token? Что там дальше?
// '=' ? не, все равно не понятно! это все еще может быть 'id=...' и 'token=...'
// Разбирайте сами свое выражение :(

Обнаружение подобных ситуаций происходит уже на этапе компиляции грамматики. Парсер не сможет определить, как трактовать текущий терминал ('x' в последнем примере) ни по текущему состоянию, ни с использованием следующего символа. И вот эта ситуация называется 'reduce/reduce conflict'. (кстати, ант на reduce/reduce жалуется? Если я не угадал и там shift/reduce, нужно писать другой пример

).

Общего универсального решения для проблемы reduce/reduce нет. В некоторых случаях можно преобразовать грамматику. В более сложных случаях ничего сделать нельзя. Приемы обычно описываются в тех же учебниках и конспектах лекций рядом с описанием LR парсеров.

По неточному фрагменту грамматики полезное решение угадать нельзя. Хорошо бы было посмотреть всю грамматику целиком. Если она не секретная, может выложите куда-нибудь? Ну а если секретная, попробуйте сами теорию почитать. Там ничего сложного, просто более подробное описание процесса выше (и с описанием различных граничных случаев) со стандартными приемами решения разных конфликтов.

Здравствуйте, maxkar, Вы писали:

M>Здравствуйте, Кондраций, Вы писали:

К>>Вопрос первый: можно ли как-то использовать '=', а не '=='. Можно конечно парсером выдирать всё выражения и разбирать далее руками, но не хочется.
К>>Вопрос второй на понимание (может смешной, но я в грамматиках лох): описанное выше проиходит от того, что ANTLR описывает контекстно-свободные грамматики?

M>Начну со второго вопроса. Описанное выше просиходит из-за того, что ANTLR не разбирает произвольные контекстные грамматики. Он разбирает LR(1) (или LALR, не помню уже) грамматики, которые являются подмножеством контекстно-свободных.

...

Спасибо, тут есть над чем подумать.

M>Обнаружение подобных ситуаций происходит уже на этапе компиляции грамматики. Парсер не сможет определить, как трактовать текущий терминал ('x' в последнем примере) ни по текущему состоянию, ни с использованием следующего символа. И вот эта ситуация называется 'reduce/reduce conflict'. (кстати, ант на reduce/reduce жалуется? Если я не угадал и там shift/reduce, нужно писать другой пример

).
Не, он жалуется на MismatchedTokenException, таких умных слов, как у Вас, он не говорил

M>По неточному фрагменту грамматики полезное решение угадать нельзя. Хорошо бы было посмотреть всю грамматику целиком. Если она не секретная, может выложите куда-нибудь?

Секретного ничего нет, она просто большая и с семантикой. Читать сложно. Я подготовил краткий пример.
Данный пример отрабатывает номально, но если заменить '==' на '=' в правиле лексера WhereOperator и в разбираемом тексте, то будет то, о чём я и говорил. Заходное правило — parse.

Граматика

grammar Example;

options {
      language = CSharp3;
}


ID  :    ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
    ;

INT :    '0'..'9'+
    ;

WS  :   ( ' '
        | '\t'
        | '\r'
        | '\n'
        ) {$channel=HIDDEN;}
    ;


QUOTE     :    '"';

QuotedString :    QUOTE (~QUOTE)* QUOTE ;

quotedString :    QuotedString; // Выделено правило парсера для того, чтобы можно было вставить свой код (symantyc action)


where : 'where' '(' (whereRec (',' whereRec)*)?  ')';

WhereOperator    :    '==' | '<>' | '>' | '<' | '>=' | '<=';


whereRec :  
    ID  WhereOperator  (  quotedString | INT  )  
    ;


assign    :    ID '=' (quotedString | INT | ID) where? ;

parse    :
    assign+
 ;

	Пример
	`var1 = 11 var2 = "string" where( var1 > 3, varN == 4) var3 = var1`

У меня и было такое хотение, чтобы при выполнении правила парсера where лексер определял, что втретившийся знак '=' — это WhereOperator. Но лексер работает перед парсером...

Обходной путь наверное таков:

WhereOperator    :    '<>' | '>' | '<' | '>=' | '<=';

whereRec :  
    ID  (WhereOperator | '=' ) (  quotedString | INT  )  
    ;

Парсер не ругается. Наверное, так и сделаю.

Здравствуйте, Кондраций, Вы писали:

К>Данный пример отрабатывает номально, но если заменить '==' на '=' в правиле лексера WhereOperator и в разбираемом тексте, то будет то, о чём я и говорил. Заходное правило — parse.
Немного не понял: ошибка возникает в сосент трансляции грамматики в код или уже потом на этапе разбора?
Просто сама трансляция у меня прошла на ура, я использовал порт ANTLR на C# 3-ей версии

Здравствуйте, Михаил Романов, Вы писали:

МР>Здравствуйте, Кондраций, Вы писали:

К>>Данный пример отрабатывает номально, но если заменить '==' на '=' в правиле лексера WhereOperator и в разбираемом тексте, то будет то, о чём я и говорил. Заходное правило — parse.
МР>Немного не понял: ошибка возникает в сосент трансляции грамматики в код или уже потом на этапе разбора?
МР>Просто сама трансляция у меня прошла на ура, я использовал порт ANTLR на C# 3-ей версии
Я использую графический ANTLRWorks 1.5.2, там внизу есть закладка "Interpreter". В ней я постоянно тестирую грамматику в процессе написания. Вот в ней и даёт исключение.
Трансляция также проходит на "ура" в любом случае, но в рантайме даёт ошибку. Т.е. терминал лексер распознаёт, но тип токена даёт не тот, что нужен бы: '=', а не WhereOperator. А уже парсер видит, что вместо WhereOperator приходит нечто иное, — и ругается.

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

Я склоняюсь к тому, что хочу невозможного. Лексер честно потрошит вход на токены, а вот соответствие токенов между собой — зона ответственности парсера. Парсер же работает позже лексера, посему у лексера просто нет возможности узнать, какого типа токен нужен парсеру в конкретный момент. Т.е. нужно пользоваться обходным путём и не жужжать

	От:	Кондраций
	Дата:	02.12.15 20:18
	Оценка:

	От:	maxkar
	Дата:	03.12.15 23:40
	Оценка:	61 (3)

	От:	Кондраций
	Дата:	04.12.15 06:15
	Оценка:

От:	Михаил Романов	https://mihailromanov.wordpress.com/
Дата:	04.12.15 15:26
Оценка:

	От:	Кондраций
	Дата:	04.12.15 16:34
	Оценка:

	От:	_DAle_
	Дата:	15.12.15 07:28
	Оценка:	6 (1)