Здравствуйте, Кондраций, Вы писали:
К>Вопрос первый: можно ли как-то использовать '=', а не '=='. Можно конечно парсером выдирать всё выражения и разбирать далее руками, но не хочется. К>Вопрос второй на понимание (может смешной, но я в грамматиках лох): описанное выше проиходит от того, что 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)']
Но так происходит только в простом случае. Для более сложной грамматики по текущему стеку не всегда можно определить, во что сворачивается (по какому правилу заменяется) терминал. Например:
В этом случае выражение '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 не разбирает произвольные контекстные грамматики. Он разбирает LR(1) (или LALR, не помню уже) грамматики, которые являются подмножеством контекстно-свободных.
Пишу парсер некоего самопального конфига. В конфиге среди прочего встречаются в вещи типа filter = "тут какая-то строка". Соответственно в грамматике это выглядит примерно так id '=' quotedString.
Но внезапно возникла необходимость включить в конфиг (и соответственно — парсить) некие простейшие выражения типа таких QQ > 1, AA < 10, ZZ = "это строка". Нарисовал правила типа такого (пишу по памяти): Int: (0..9)+; Operation: '='|'<'|'>'|''<=|'>='|'<>'; expr: token Operation (Int | quotedString) ;
Ругается на '='. Если для обозначения операции равенства использовать '==', то всё работает.
Лексер и парсер описываются в одном файле грамматики.
Вопрос первый: можно ли как-то использовать '=', а не '=='. Можно конечно парсером выдирать всё выражения и разбирать далее руками, но не хочется.
Вопрос второй на понимание (может смешной, но я в грамматиках лох): описанное выше проиходит от того, что ANTLR описывает контекстно-свободные грамматики? Т.е. если символ/токен где-то используется для одного действия (у меня для обозначения присвоения), то в другом значении его использовать нельзя. А была-бы контекстно связанная, то значение символа/токена могло бы зависть бы от контекста, и тогда бы разборе выражения был бы (можно было бы сделать) другой контекс со своим значением символа '='. Так?
Сообщение заговорено потомственным колдуном, целителем и магом в девятом поколении!
Модерирование или минусование сообщения ведет к половому бессилию, венерическим заболеваниям, венцу безбрачия и диарее!
Здравствуйте, 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+
;
У меня и было такое хотение, чтобы при выполнении правила парсера where лексер определял, что втретившийся знак '=' — это WhereOperator. Но лексер работает перед парсером...
Сообщение заговорено потомственным колдуном, целителем и магом в девятом поколении!
Модерирование или минусование сообщения ведет к половому бессилию, венерическим заболеваниям, венцу безбрачия и диарее!
Здравствуйте, Кондраций, Вы писали:
К>Данный пример отрабатывает номально, но если заменить '==' на '=' в правиле лексера WhereOperator и в разбираемом тексте, то будет то, о чём я и говорил. Заходное правило — parse.
Немного не понял: ошибка возникает в сосент трансляции грамматики в код или уже потом на этапе разбора?
Просто сама трансляция у меня прошла на ура, я использовал порт ANTLR на C# 3-ей версии
Здравствуйте, Михаил Романов, Вы писали:
МР>Здравствуйте, Кондраций, Вы писали:
К>>Данный пример отрабатывает номально, но если заменить '==' на '=' в правиле лексера WhereOperator и в разбираемом тексте, то будет то, о чём я и говорил. Заходное правило — parse. МР>Немного не понял: ошибка возникает в сосент трансляции грамматики в код или уже потом на этапе разбора? МР>Просто сама трансляция у меня прошла на ура, я использовал порт ANTLR на C# 3-ей версии
Я использую графический ANTLRWorks 1.5.2, там внизу есть закладка "Interpreter". В ней я постоянно тестирую грамматику в процессе написания. Вот в ней и даёт исключение.
Трансляция также проходит на "ура" в любом случае, но в рантайме даёт ошибку. Т.е. терминал лексер распознаёт, но тип токена даёт не тот, что нужен бы: '=', а не WhereOperator. А уже парсер видит, что вместо WhereOperator приходит нечто иное, — и ругается.
На всяк случай напомню, что я выложил корректный пример. Чтобы получить обсуждаемое поведение, нужно в грамматике и в примере для разбора заменить '==' на '='.
Я склоняюсь к тому, что хочу невозможного. Лексер честно потрошит вход на токены, а вот соответствие токенов между собой — зона ответственности парсера. Парсер же работает позже лексера, посему у лексера просто нет возможности узнать, какого типа токен нужен парсеру в конкретный момент. Т.е. нужно пользоваться обходным путём и не жужжать
Сообщение заговорено потомственным колдуном, целителем и магом в девятом поколении!
Модерирование или минусование сообщения ведет к половому бессилию, венерическим заболеваниям, венцу безбрачия и диарее!
Здравствуйте, novitk, Вы писали:
N>Здравствуйте, Кондраций, Вы писали:
N>WhereOperator не должен быть правилом лексера. Поменяй на правило парсера whereOperator (маленькая 'w') и будет счастье.
Точно! А казалось бы — очевидно...
Спасибо!
Сообщение заговорено потомственным колдуном, целителем и магом в девятом поколении!
Модерирование или минусование сообщения ведет к половому бессилию, венерическим заболеваниям, венцу безбрачия и диарее!