Yacc&Lex

← →
pasha_golub © (2005-06-16 15:55) [0]

Хочу произвести опрос с вашего позволения.

Как часто господам в их разработках требуется системы подобного рода?

1. Не требуется
2. Пишу вручную
3. Требуется. Пользуюсь версией для С
4. Было бы замечательно иметь версию для Делфи

В каком виде?
1. Стандартные возможности Yacc-Lex
2. Стандартные плюс постройка дерева разбора (автоматически внутре анализа)
3. Просто проверка синтаксиса

Ну, и ежели кто пользуется, то опишите, пожалуйста, область применения. Спасибо.

← →
inic © (2005-06-16 16:40) [1]

1
-

PS Буду интересоваться через 3-4 месяца по личным причинам.

← →
Alexander Panov © (2005-06-16 16:43) [2]

А что это такое?

← →
matt © (2005-06-16 16:49) [3]

вроде системы автоматического построения компиляторов-интерпритаторов

← →
MOA © (2005-06-16 16:50) [4]

Пользовался однажды, лет 10-12 назад.
Версия на Delphi, ПСМС, не нужна - если человек может пользоваться - ему без разницы, на чём ;), а на С(++,#) понадёжнее всё-же.

← →
MOA © (2005-06-16 16:55) [5]

2Alexander Panov
YACC - компилятор компиляторов (полностью - ещё один компилятор компиляторов). От предыдущих отличался(-ается) возможностью разбора грамматик с правилами (например, вложенные IF) и управлением свёртками.
LEX - генератор лексических анализаторов
(бывают версии - bison и flex, например, т.к. yacc и lex - торговые марки ATT).

← →
Petr V. Abramov © (2005-06-16 16:58) [6]

> pasha_golub © (16.06.05 15:55)
> 2. Стандартные плюс постройка дерева разбора (автоматически внутре анализа)
Паша, колись, чего задумал?

← →
Игорь Шевченко © (2005-06-16 17:04) [7]

3.

Требовалось один раз, был написан анализатор SQL.

← →
Андрей Жук © (2005-06-16 17:07) [8]

> Паша, колись, чего задумал?

Он же компоненты доступа к некоей БД пишет...

← →
Digitman © (2005-06-16 17:09) [9]

> 4. Было бы замечательно иметь версию для Делфи

в принципе широкоизвестный TP Lex&Yacc не так уж и сложно адаптировать для работы в Делфи ... но уж больно много там рутинной возни получается ...

← →
Zer0 © (2005-06-21 15:01) [10]

есть более удобные варианты, например http://www.devincook.com/goldparser/

← →
pasha_golub © (2005-06-21 15:49) [11]

Petr V. Abramov © (16.06.05 16:58) [6]
Вот его и задумал. ;0) Есть идейка выбрать эту тему в качестве научной работы, плюс выяснить будет ли система пользоваться спросом.

Digitman © (16.06.05 17:09) [9]
Есть такое. Рутины до черта.

Zer0 © (21.06.05 15:01) [10]
Могу кинуть грамматику, которую за 12 часов не скомпилирует. Общался с автором.

1. Плюс нету приоритета операций, что немаловажно ибо редко кто пишет "академическую" грамматику.

2. Много грамматик уже есть, писанных на Yacc"е только под С. Переписывать их надо ибо пункт 1.

3. Лексический анализатор встроенный. Нету возможности скормить свой. Встроенный же разбирает только через DFA (конечный автомат). А некоторые грамматики позволяют вольности, например:

CREATE PROCEDURE ... $BODY$ ... $SUB_BODY$ ... $SUB_BODY$ ... $BODY$

Внутри $..$ может стоять любой правильный идентификатор. Разрулить на уровне собвенного лексического анализатора можно. Стандартными средствами его не описать.

А ежели писать грамматику с нуля, то да. Очень хорошая система.

← →
TUser © (2005-06-21 15:55) [12]

> 4. Было бы замечательно иметь версию для Делфи

Есть GOLD. Яндексом только вот найти никак не могу, но дома посмотрю ссылку.

← →
pasha_golub © (2005-06-21 15:56) [13]

TUser © (21.06.05 15:55) [12]
Вот это?
http://www.devincook.com/goldparser/

← →
Petr V. Abramov © (2005-06-21 17:14) [14]

> pasha_golub © (21.06.05 15:49) [11]
Паша, ты будешь смеяться, я тоже работаю над подобного типа задачей (в свободное время)
"Идея носится в воздухе"?

← →
pasha_golub © (2005-06-21 17:55) [15]

Petr V. Abramov © (21.06.05 17:14) [14]
Гы-гы...

Ну, не знаю как в воздухе, просто действительно понадобился парсер. И не один. Тот который более-менее подходит, во-первых, не все правильно берет, а, во-вторых, за исходники хотят 800 баксов в год.

Давай тады делиться наработками... ;0)

← →
Ермак © (2005-06-21 19:40) [16]

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

Компилятор для диалекта Oberon"а, решили делать раскрутку (то есть, писать на нем самом же), поэтому придется все вручную.

Вообще-то, этого добра сейчас полно. Есть русская разработка ZUBR.
Под Аду есть свои. Под Модулу-2.

← →
Ермак © (2005-06-21 19:53) [17]

Нда, не очень понятно написал.

"Система такого рода", "этого добра полно" - относится
к автоматическим построителям парсеров.

← →
pasha_golub © (2005-06-21 19:58) [18]

Ермак © (21.06.05 19:53) [17]
Угу. Но ведь парсеры не мультиИДЕ"шные в основном. По крайней мере, кроме GoldParser"a ничего на ум не приходит.

← →
Иван Шихалев © (2005-06-21 22:27) [19]

в принципе широкоизвестный TP Lex&Yacc не так уж и сложно адаптировать для работы в Делфи ... но уж больно много там рутинной возни получается

Версия 4.1 декларируется как совместимая с Free Pascal и Delphi.

http://www.musikwissenschaft.uni-mainz.de/~ag/tply/tply.html

← →
pasha_golub © (2005-06-21 22:49) [20]

Иван Шихалев © (21.06.05 22:27) [19]
Она-то совместима... Но.

1. Есть более новая, правда зовется уже dyacc, ну и dlex соответственно. Жаль правда, что продукт опять немножко заброшен.

2. Реализация процедурная, то есть: много глобальных переменных, констант, и т.д., и т.п.

3. Есть некоторые помарки (багами их не поворачивается язык назвать)

4. Ну и есть поле для усовершенствования. Допустим, есть дублирущиеся данные, которые при большой грамматике вылазят боком.

Вопрос такой:
1. Интересуют ли господ-программистов уже готовые парсеры? Если да, то что именно хотелось бы разобрать?

2. В каком виде? Имеется ввиду, просто дерево ли, или по косточкам с разжевыванием?

← →
Alex Konshin © (2005-06-21 22:58) [21]

Я все время писал свои. В принципе у меня даже есть(был?) свой компилятор грамматик на Delphi. А так как сейчас пишу на Java то и все нароботки сейчас на ней. Тоже есть уже есть свои интерпретаторы , макропроцессоры и т.п....

← →
Petr V. Abramov © (2005-06-22 00:34) [22]

> pasha_golub © (21.06.05 17:55) [15]
Давай. Будете у нас на Колыме... :)

← →
pasha_golub © (2005-06-22 10:33) [23]

Alex Konshin © (21.06.05 22:58) [21]
А можно ознакомиться? Честность и порядочность гарантирую. :0)

Petr V. Abramov © (22.06.05 00:34) [22]
Тады гоу в аську. :)

pasha_golub © (22.06.05 10:33) [23]
Alex Konshin © (21.06.05 22:58) [21]
А можно ознакомиться? Честность и порядочность гарантирую. :0)

С чем именно? Если компилятор грамматик, то он прямо сказать своеобразный. И хуже того, я его не закончил (как раз делал его перед отъездом сюда), хотя сам он работал.
Грамматика компиллировалась в некий псевдокод, причем сам компилятор был не на Delphi (я тогда предполагал, что я перепишу его на нем самом, т.е. я хотел сделать раскрутку). Полученный псевдокод - лексический анализатор интерпретировался. Т.е. разбор входного текста делал интерпретатор, а программа для него было на псевдокоде, который получался после компиляции грамматики. Кажется, теперь должны быть понятно. Сам разбор тоже был хитрым. Автоматически понимались места неоднозначностей и происходило ветвление и оба варианта разбора генерировались (виртуально) параллельно до тех пор, пока какие-то альтернативы не умирали. Таким образом должны были пониматься не совсем правильные "контекстные" грамматики, где нужно смотреть вперед.
Как ни странно, работало очень быстро, правда я реально это делал для реализации интерпретатора, поэтому и примеры у меня были конкретные. То есть, я не ставил задачу компиляции и разбора любой грамматики. Задача была сделать интерпретатор для языка, синтаксис которого я еще и сам не совсем представлял, т.е. могли быть существенные изменения.
Сейчас попытался понять, в каком состоянии этот проект, даже пока не понял, как запустить это все, как будто не сам писал. :)

Если вопрос был про java, то это интерпретатор имеется и он точно работает :), потому как является частью нескольких моих текущих проектов.

Нет, вопрос был про Делфи. Объяснение еще больше запутало. :0)

Ну не знаю как объяснить...
Грамматика - некий входной текстовый файл.
Была программка (не на Delphi), которая исходя из этого файла строила исходники на Deplhi (точнее, набор таблиц, одна из которых по сути есть программа на псевдокоде для анализатора).
После копиляции полученых исходников мы получаем лексический аналилизатор языка, описанного грамматикой. Только сам этот полученный анализатор на самом деле является интерпретатором с зашитой в нем программой на псевдокоде. Считай, что у меня создана некая виртуальная машина, ориентированная для синтаксического разбора, а программы для нее - на этом самом псевдокоде. Естественно, псевдокод сделан так, чтоб он быстро исполнялся и в тоже время легко получался из входной грамматики.
Попробую привести примеры файлов:

Вот какой-то из примеров описания грамматики:
# Тестовое описание синтаксиса # Установки для генератора таблиц парсера: %out="ParserTables.inc" %interface="ParserInterface.inc" %parserclass="TAcntParser" #lex_def_sign=":" # Также можно переопределить префиксы. По умолчанию принимаются следующие значения: #TermPrefix="trm" #CharPrefix="chr" #LexPrefix="lxm" #TypePrefix="typ" #LocFlagPrefix="lflg" %symbols # Символы. # Формат: # имя[>функция] символы # Если вместо имени фунции указана *, то имя символа используется # как имя процедуры. # В программе к имени процедуры добавляется префикc "Char". Digit>* 0-9 Alpha>* a-z A-Z _ Blank>* \32 \t \11 \12 EOL>* \r \n EOF \0 Plus + Minus - Slash / Percent % Asterisk * Power ^ OpenBr ( CloseBr ) OpenIndex [ CloseIndex ] Equ = Colon : Semicolon ; Comma , Dot . Tilda ~ Apostrophe>CharPasStringConst \" #Quote>CharCStringConst \" BackApostrophe ` Less < More > ComAt @ Dollar $ Diez # Ampersand & Line | OpenBlock { CloseBlock } Ask ? Not ! BackSlash \\ %terms #--------------------------------------------------- # Термы - атомы языка. EOF EOF EOL EOL Blank Blank Plus Plus Minus Minus FloatDiv Slash IntegerDiv "div" IntegerMod "mod" Percent % Mult Asterisk Power ** Indirect ^ OpenBracket ( CloseBracket ) OpenIndex [ ClosIndex ] Colon Colon Semicolon Semicolon Comma Comma Dot Dot More > Less < ShiftLeft << ShiftRight >> Equ Equ Assign := NoLess >= NoMore <= NotEqu <> BitAnd & BitOr | BitXor ^ BitNot ~ Not ! And && Or || Increment ++ Decrement -- PlusAssign += MinusAssign -= MultAssign *= DivAssign /= LineComment>* // StreamComment>* /* Func "function" Begin "begin" End "end" If "if" Else "else" Endif "endif" While "while" For "for" To "to" DownTo "downto" #Do { #EndDo } Do "do" IntegerType "Integer" StringType "String" FloatType "Float" BooleanType "Boolean" Const "const" Var "var" True "True" False "False" # Эти термы опознаются процедурами обработки символов или других термов Identifier StringConst IntegerConst FloatConst StringSymConst IntegerSymConst FloatSymConst BooleanSymConst FloatVar IntegerVar StringVar BooleanVar #----------------------------------------------------------------------- # Базовые типы и неявные преобразования типов. # Это список типов данных с точки зрения синтаксиса, он не обязательно должен # (а обычно - не должен) соответствовать списку базовых типов языка. # По сути они являются неким аттрибутом значений лексем и выражений, что # позволяет еще на этапе синтаксического разбора делать предварительную # проверку соответствия типов данных без существенного усложнения описания # синтаксиса. # Справа от имени - список типов, в которые он преобразуется неявно. # Тип Void уже описан. %types Integer Float Float String Array Boolean Array #Record #Object #Class

#----------------------------------------------------------------------- # Описание синтаксиса # # +имя_флага - Установить локальный флаг. Изменение действует до конца текущей лексемы. # -имя_флага - Сбросить локальный флаг. Изменение действует до конца текущей лексемы. # =тип - Установить текущий тип. # >имя_метода - Вызов метода объекта-парсера. Тип метода должен быть TParserProbeFunc. # [список_типов] - Текщий тип должен быть одним из указанных, в противном случае # текущая нить обрывается. # %команда # # Команды: # %abort - Обрывает текущую нить. # %passtype - Тип из предыдущей лексемы становится текущим. # %matchtype - Тип из предыдущей лексемы cопоставляется с текущим. Если существует тип, # к которому их можно неявно преобразовать, то этот тип становится текущим. # В противном случае текущая нить обрывается. Команда обычно применяется для сопоставления # типов операндов бинарных операций. # %lmatchtype - Тип из предыдущей лексемы должен быть неявно приводимым к текущему. # В противном случае текущая нить обрывается. Команда обычно применяется для сопоставления # типов в лексемах вроде присваивания. # %rmatchtype - Текущий тип должен быть неявно приводимым к типу из предыдущей лексемы. # В противном случае текущая нить обрывается. # %if условие - Если условие - истина, то выполняется следующий токен или блок (в круглых # скобках), если нет - пропускается. После этого токена или блока может быть команда # %else, тогда следующий за ней токен или блок выполняется только при ложном значении # условия. В качестве условия может быть либо имя_терма, либо ?имя_флага, # либо [список_типов]. # Непосредственно перед условием может быть символ "!" - отрицание. # %while условие - Пока условие - истина выполняется следующий терм или блок. # %syntax # Выражения RValue : %if ?Constant %abort ( IntegerVar | FloatVar | BooleanVar | StringVar ) %passtype | IntegerConst %passtype | IntegerSymConst %passtype | FloatConst %passtype | FloatSymConst %passtype | (True|False) =Boolean | OpenBracket Expression %passtype CloseBracket # | Assignment %passtype | Minus RValue %passtype [Integer,Float] | BitNot RValue %passtype [Integer] | Not RValue %passtype [Boolean] # | IntegerType OpenBracket Expression CloseBracket =Integer Expression : ExpressionPrio2 %passtype | ExpressionPrio2 %passtype [Boolean] ( Or | And ) ExpressionPrio2 %matchtype ExpressionPrio2 : ExpressionPrio4 %passtype | ExpressionPrio4 %passtype [Integer,Float,String] ( More | Less | Equ | NoLess | NoMore | NotEqu ) ExpressionPrio4 %matchtype =Boolean ExpressionPrio4 : ExpressionPrio4 %passtype ( Plus | Minus ) ExpressionPrio6 %matchtype | ExpressionPrio6 %passtype ExpressionPrio6 : ExpressionPrio6 %passtype [Integer] ( Mult | IntegerDiv | IntegerMod | ShiftLeft | ShiftRight | BitAnd | BitOr | BitXor ) RValue %matchtype | ExpressionPrio6 %passtype [Float] ( Mult | FloatDiv ) RValue %matchtype | RValue %passtype ForLoop : For IntegerVar Assign Expression %passtype [Integer] ( To | DownTo ) Expression %passtype [Integer] Do Statement =Void WhileLoop : While Expression %passtype [Boolean] Do Statement =Void #ConditionalExpression # : If Expression %passtype [Boolean] Do Statements EndDo # ( ElseIf # (| Else Do Statements EndDo) Type : IntegerType =Integer | StringType =String | FloatType =Float # Придется именно здесь исполнять описание во время синтаксического разбора (в методе), # т.к. новый идентификатор может быть уже использован в выражениях при описании # следующих идентификаторов еще до конца лексемы Declaration. # В методе также будет проверен тип инициализирующего значения. DeclarationIdentifier >* : Identifier | Identifier Colon +Constant Expression DeclarationIdentifiers : DeclarationIdentifier | DeclarationIdentifier Comma %again Declaration : Type %passtype DeclarationIdentifiers ClosedStatement : ForLoop | WhileLoop | Begin Statements %passtype End LValue : ( IntegerVar | FloatVar | StringVar | BooleanVar ) %passtype Assignment : LValue %passtype Assign Expression %lmatchtype Statement : Assignment %passtype | ClosedStatement | Declaration # %passtype добавлен для составных предложений, выдающих результат Statements : Statement %while Semicolon Statement %passtype %end

Это часть псевдокода (точнее, это уже исходник для Delphi), что получается:
ParserRobotProgram : Array [0..255] of TParserRobotCmd = ( { 0} ( Code: chkterm; Trm: trmEOF ), { 1} ( Code: jump; Ads: 0 ), // RValue : { 2} ( Code: fork; Ads: 17 ), { 3} ( Code: ifflag; Flg: lflgConstant ), { 4} ( Code: abort ), { 5} ( Code: ifnotterm; Trm: trmFloatVar ), { 6} ( Code: jump; Ads: 8 ), { 7} ( Code: jump; Ads: 15 ), { 8} ( Code: ifnotterm; Trm: trmBooleanVar ), { 9} ( Code: jump; Ads: 11 ), { 10} ( Code: jump; Ads: 15 ), { 11} ( Code: ifnotterm; Trm: trmIntegerVar ), { 12} ( Code: jump; Ads: 14 ), { 13} ( Code: jump; Ads: 15 ), { 14} ( Code: chkterm; Trm: trmStringVar ), { 15} ( Code: passtype ), { 16} ( Code: ret ), { 17} ( Code: ifnotterm; Trm: trmFloatConst ), { 18} ( Code: jump; Ads: 21 ), { 19} ( Code: passtype ), { 20} ( Code: ret ), { 21} ( Code: fork; Ads: 28 ), { 22} ( Code: ifnotterm; Trm: trmFalse ), { 23} ( Code: jump; Ads: 25 ), { 24} ( Code: jump; Ads: 26 ), { 25} ( Code: chkterm; Trm: trmTrue ), { 26} ( Code: settype; Typ: typBoolean ), { 27} ( Code: ret ), { 28} ( Code: ifnotterm; Trm: trmFloatSymConst ), { 29} ( Code: jump; Ads: 32 ), { 30} ( Code: passtype ), { 31} ( Code: ret ), { 32} ( Code: ifnotterm; Trm: trmBitNot ), { 33} ( Code: jump; Ads: 38 ), { 34} ( Code: lexeme; Lex: lxmRValue ), { 35} ( Code: passtype ), { 36} ( Code: checktype; Msk: [ typInteger ] ), { 37} ( Code: ret ), { 38} ( Code: ifnotterm; Trm: trmIntegerConst ), { 39} ( Code: jump; Ads: 42 ), { 40} ( Code: passtype ), { 41} ( Code: ret ), { 42} ( Code: ifnotterm; Trm: trmIntegerSymConst ), { 43} ( Code: jump; Ads: 46 ), { 44} ( Code: passtype ), { 45} ( Code: ret ), { 46} ( Code: ifnotterm; Trm: trmMinus ), { 47} ( Code: jump; Ads: 52 ), { 48} ( Code: lexeme; Lex: lxmRValue ), { 49} ( Code: passtype ), { 50} ( Code: checktype; Msk: [ typInteger, typFloat ] ), { 51} ( Code: ret ), { 52} ( Code: ifnotterm; Trm: trmNot ), { 53} ( Code: jump; Ads: 58 ), { 54} ( Code: lexeme; Lex: lxmRValue ), { 55} ( Code: passtype ), { 56} ( Code: checktype; Msk: [ typBoolean ] ), { 57} ( Code: ret ),
Ну и так далее...
Естественно, это лишь одна из таблиц. Есть еще таблицы символов, термов и т.п..

Это команды псевдокода:
TParserRobotCmdCode = ( // Вилка - разделение нити на две. Одна продолжает выполнение со следующей команды, // вторая с указанного адреса. fork, // Вызов программы указанной лексемы. lexeme, // Обрыв нити, если очередной терм не тот, что требуется. chkterm, // Если очередной терм тот, что указан, то пропускаем следующую команду (обычно это jump или ret). ifnotterm, // Если очередной терм тот, что требуется, то выполняем следующую команду, // в противном случае она будет пропущена. ifterm, // Переход - задает адрес следующей команды. jump, // Завершение текущей лексемы. ret, // Вызов метода. Тип метода должен быть TParserProbeFunc. call, // Установка локального флага. setflag, // Сброс локального флага. resetflag, // Если указанный локальный флаг установлен, то будет выполнена следующая команда, // в противном случае она будет пропущена. ifflag, // Если указанный локальный флаг НЕ установлен, то будет выполнена следующая команда, // в противном случае она будет пропущена. ifnotflag, // Обрыв текущей нити. abort, // Явная установка текущего типа (поля FCurrentRobotThread^.CurrentDataType). settype, // Установка текущего типа по типу последней лексемы. passtype, // Сопоставление текущего типа и типа последней лексемы: // если они не равны, то ищется тип, к которому они оба могут быть приведены. // Если их можно привести к одному типу, то этот тип становится текущим, // в противном случае текущая нить синтаксического разбора умирает. matchtype, iftype, ifnottype, checktype );

Да, кстати, слово нить никакого отношения к TThread не имеет. Это по сути нити в виртуальной машине, но это не нити Win32 API.

Однако, блин. Впечатляет!

И что разруливает все неоднозначности при описании грамматики?

Исходная грамматика компилировалась вообще-то скриптом на REXX. Это говорит о простоте самого преобразования. Как я уже говорил, я предполагал его переписать уже на самом языке. Хотя, собственно для решения поставленной задачи это не важно: грамматика все равно компилировалась до компиляции самого интерпретатора. Но теоретически, совсем несложно было переделать это под компиляцию на лету, только не совсем понятно, зачем, разве что из академического интереса.
"Неоднозначности" разруливаются сами. То есть компилятор грамматики очень туп и прямолинеен. Я под неоднозначностями имел в виду локальные неоднозначности, например, когда некое ключевое слово понимается сильно по-разному в разных контекстах, как слово case в Паскале, или . Суть в том, что парсер пытается понять исходный текст всеми возможными способами, и когда находит, что какой-то вариант не подходит из-за некого последующего терма, то он отбрасывается ("обрыв нити"). В итоге при правильном входном тексте (и, естественно, при правильно описанной грамматике) должен остаться только один вариант, он и есть результат разбора.
Если остается несколько вариантов, то это значит, что сама грамматика неоднозначна. Если ни одного, то значит, что входной текст не соответствует грамматике. Это так, грубо.
Результат разбора у меня - некое дерево разбора и некий псевдокод (я предполагал сохранять скомпилированый код). Кстати, занятно, что описания грамматик того же Паскаля, что обычно приводятся в книжках, на самом деле неверны - они неоднозначны, и неоднозначность возникает из-за неявных приведений типов операндов. Именно поэтому мне пришлось ввести понимание типов операндов и неявного приведения уже в сам парсер. Вообще-то принято это делать позднее, но тогда парсер получается нетипизированым и не может отловить ошибки несовместимости типов.

Что-то как-то нет этуазизма это дописать. Я помню, что я остановился на генерации псевдокода (того, что получается при компиляции входной программы на нашем языке). То есть, если бы я делал просто интерпретатор, то он уже бы работал. Но мы же не ищем легких путей :). Мне же нужно было, чтобы псевдокод не содержал абсолютных ссылок, чтоб можно его было сохранять где-нибудь на диске или в базе, чтобы он был компактным и чтобы можно было закодировать сложные конструкции объектного языка со строгой типизацией. Я предполагал задействовать этот интерпретатор на промежуточном звене многозвенки.

Yacc&amp;Lex Найти похожие ветки

Yacc&Lex Найти похожие ветки