Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Hello, World!
  
 

Фильтр по датам

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
  
 
Во Флориде и в Королевстве сейчас  07:14[Войти] | [Зарегистрироваться]

Обсуждение материала
Введение в теорию синтаксического анализа
Полный текст материала


Другие публикации автора: Антон Григорьев

Цитата или краткий комментарий:

«... Данная статья является введением в теорию синтаксического анализа выражений. Переходя от простых примеров к сложным, мы построим полноценный калькулятор, способный рассчитать заданное арифметическое выражение с учётом приоритетов операций, с использованием функций и переменных, с возможностью изменения приоритета с помощью скобок. Все примеры даются на языке Delphi и сопровождаются экскурсами в теорию, объясняющими, как эти примеры работают. ...»


Важно:
  • Страница предназначена для обсуждения материала, его содержания, полезности, соответствия действительности и так далее. Смысл не в разборке, а в приближении к истине :о) и пользе для всех.
  • Любые другие сообщения или вопросы, а так же личные эмоции в адрес авторов и полемика, не относящаяся к теме обсуждаемого материала, будут удаляться без предупреждения авторов, дабы не мешать жителям нормально общаться.
  • При голосовании учитывайте уровень, на который расчитан материал. "Интересность и полезность" имеет смысл оценивать относительно того, кому именно предназначался материал.
  • Размер одного сообщений не должен превышать 5К. Если Вам нужно сказать больше, сделайте это за два раза. Или, что в данной ситуации правильнее, напишите свою статью.
Всегда легче осудить сделанное, нежели сделать самому. Поэтому, пожалуйста, соблюдайте правила Королевства и уважайте друг друга.



Добавить свое мнение.

Результаты голосования
Оценка содержания

  Содержит полезные и(или) интересные сведения
[1]1894.7%
 
  Ничего особенно нового и интересного
[2]15.3%
 
  Написано неверно (обязательно укажите почему)
[3]00%
 
Всего проголосовали: 19

Оценка стиля изложения

  Все понятно, материал читается легко
[1]1583.3%
 
  Есть неясности в изложении
[2]211.1%
 
  Непонятно написано, трудно читается
[3]15.6%
 
Всего проголосовали: 18




Смотрите также материалы по темам:
[Синтаксический анализ, разбор выражений, парсинг] [Ядро, структуры и механизмы Windows, использование API] [Разбор и вычисление выражений]

Комментарии жителей
Отслеживать это обсуждение

Всего сообщений: 40

16-06-2010 14:37
Статье уже 11 лет, а её всё читают.
Тоже читаю. Написано понятно. Мне нравится. Может, есть продолжение?
А там уже и до книжки недалеко. :-)


26-05-2009 08:03
"Милый мой, хороший, догадайся сам" ;-)

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

>>> (5*---3) != (5*-(-(-3)))
То есть, Вы хотите сказать, что эти две записи неэквивалентны. А чем Вы при этом руководствуетесь? Тем, как учили писать в школе? Вообще-то, форму записи можно придумать свою, если она позволяет решать поставленную задачу. Надо только ее формально определить. Антон это сделал. Так что вот такое выражение в его грамматике
5*---3
соответствует вот такому выражению, записанному по правилам записи выражений, которым учат в школе
5*(-(-(-3)))

Я бы для придирки написал что-то более веселое. Например
5++--++3
Этакий Си-образный закидон ;-)
Но даже в этом случае из грамматики однозначно следует, что первый знак - это знак бинарной операции, а остальные плюсы с минусами - это знаки последовательного применения ко второму операнду соответствующих унарных операций.
 Geo


26-05-2009 06:43
сообщение от автора материала
Sergey, в упор не вижу, что вам не нравится. Может, вы всё-таки напишете хотя бы небольшой комментарий?


26-05-2009 06:10
(5*---3) != (5*-(-(-3)))

<Factor> ::= <UnaryOp> <Base> ['^' <Factor>] | <Base> ['^' <Factor>]


<Factor> ::= <UnaryOp> <Factor1> | <Factor1>
<Factor1> ::= <Base> ['^' <Factor>]


26-05-2009 05:43
to Sergey:
А когда Вы в начальной школе проходили арифметические операции с отрицательными числами, Вам не приходилось решать примеры вида:
5-(-(-2))=?

Если правильно понимать язык, который Антон положил в основу калькулятора, то выражение, которое Вы привели, особых проблем не вызывает
(5*-+-+3) = 15

Форма записи, конечно, непривычная. Ну и бог с ней. Все же это учебный материал, а не готовое решение. Если разрабатывать грамматики с учетом расстановки скобок для отрицательных чсисел, которые стоят не на первом месте (а именно так требовалось оформлять выражения в школе), то получились бы более сложные правила. Как следствие, было бы труднее понимать начинающим.
 Geo


26-05-2009 04:45
<Factor> ::= <UnaryOp> <Factor> | <Base> ['^' <Factor>]
=>
(5*-+-+3) ?


10-04-2009 21:27
огромное спасибо за грамотную статью. Давно уже читал и вот сейчас пришлось вернуться


07-11-2008 02:01
>Антон, можно я добавлю ссылку на свою статью на королевстве со схожей тематикой

Фу.. как не красиво.

Алексей, Ваша заметка, это не статья, это ваш пиар.

Если вы что-то считаете своим ноу-хау, то сделайте ссылку, но примеры должны быть самодостаточными, IMHO.

А в таком виде пользы для сообщетства не несет практически никакой, в основном из-за наличия закрытого кода.

И то, что статья Антона интересна людям, а Ваша - нет, лучшее тому иллюстрация.

:-)

PS. Тем более, что таких "know-how" как грязи.. те качественных интерпретаторов и компиляторов с исходниками, в том числе и на Pascal.
Не думаю, что вы там генерируете высокооптимизированный машинный код.


06-11-2008 09:53
Антон, можно я добавлю ссылку на свою статью на королевстве со схожей тематикой
http://www.delphikingdom.ru/asp/viewitem.asp?catalogid=1019
:)


29-10-2008 13:09
сообщение от автора материала
Скажите, я что-то недопонял, или действительно, согласно рисунку допустимо только нечетное число цифр ?

Уф, дошли, наконец, руки, чтобы это исправить...

А вообще, очень приятно, что находятся люди, которые действительно разобрались в написанном настолько, чтобы замечать подобные мелочи.


17-10-2008 03:05
Очень замечательная статья. Спасибо. Некоторое вренмя назад я использовал её материал для написания компилятора математических выражений в псевдокод.
 n/a


15-10-2008 10:22
Статья отличная! Огромное спасибо автору! Искренний поклон. Предостаточно материала для освоения метода изложено в понятной форме. Еще раз спасибо.


14-10-2008 02:52
Наверно, все когда-либо задавались подобным вопросом... я еще когда учился и доступен был только лишь 286-й, написал замечательный такой объект еще на турбопаскале 6-м который позволяет применять в выражении стандартные функции и собственные переменные, которые задаются через свойство этого объекта. Помоему получилось вполне замечательно. Конечно, теория построения мне была тогда незнакома, ухватился как всегда лишь за идею.


07-10-2008 23:07
сообщение от автора материала
Скажите, я что-то недопонял, или действительно, согласно рисунку допустимо только нечетное число цифр ?

Да, это моя ошибка :( Раньше просто никто не замечал. В тех петлях, которые возвращается в цифру, своей цифры быть не должно. Исправлю в ближайшее время.


07-10-2008 20:45
Полезная статься во всех отношениях!

Скажите, я что-то недопонял, или действительно, согласно рисунку допустимо только нечетное число цифр ?


28-09-2008 23:10
сообщение от автора материала
Пишу подобную программу. Требуется поддержка функция с переменным числом аргументов

Читайте комментарии к статье, я насчёт функций с несколькими аргументами уже всё написал, читайте мои сообщения от 30-11-2006 07:53 и 09-03-2007 06:43 . Если вам этого мало, покупайте книгу, ссылка на которую стоит в начале статьи, там есть готовые функции с переменным числом аргументов.


28-09-2008 15:33
Пишу подобную программу. Требуется поддержка функция с переменным числом аргументов, а именно минимума и максимума: min(a, b, c,....,....), max(a, b, c,....,....). Подскажите, как реализовать? Заранее спасибо.


10-04-2008 10:42
сообщение от автора материала
Исправил поплывшее форматирование


09-04-2008 11:34
>>> Дело в том, что обычно в университетских курсах по информатике рассказывают только метод с преобразованием в ОПЗ
Всю жизнь считал, что в ВУЗе должны объяснять принципы, а не форму записи ;-)
 Geo


09-04-2008 07:54
>>>Не вижу я, куда и зачем тут можно прикрутить польскую нотацию. Это уже совсем другая тема, в статью она просто не вписывается.


Дело в том, что обычно в университетских курсах по информатике рассказывают только метод с преобразованием в ОПЗ.
 slow


30-01-2008 11:01
сообщение от автора материала
Dima1309:

Спасио за интересный комментарий. Честно говоря, сам я с МП-автоматами вообще не работал, а информацию о них почерпнул из книги С.З. Свердлов "Языки программирования и методы трансляции: Учебное пособие"  - СПб.: Питер, 2007. Там написано (с. 237-238), что в общем случае для контекстно-свободных грамматик может быть построен недетерминированный МП-автомат с возвратами, который эквивалентен общему алгоритму распознавания таких языков и тоже неэффективен. В честных случаях при определённых ограничениях на язык (к сожалению, Свердлов не уточняет, каких именно) для контекстно-свободной грамматики может быть построен эффективный детерминированный МП-автомат. Далее Свердлов рассматривает подкласс детерминированных МП-автоматов - табличные автоматы, и на с. 278 утверждает, что "анализатор, работающий по методу рекурсивного спуска, будет, скорее всего, быстрее табличного, интерпретирующего переходы по таблице, в то время как аналогичные переходы при рекурсивном спуске выполняются скомпилированной программой".

Как я понял из ещё одной книги (п.2 в списке литературы к статье), в тупиковые ветви заходят только недетерминированные МП-автоматы, предназначенные для разбора неоднозначной грамматики. Детерминированные автоматы, распонающие только однозначную граммтику, обходятся без таких заходов и возвратов, так что их произвоительность, видимо, будет достаточно высока, хотя Свердлов и утверждает, что всё-таки ниже, чем у метода рекурсивного спуска, т.е. Свердлов вам противоречит. Сам я, к сожалению, недостаточно хорошо знаком с МП-автоматами, чтобы рассудить, кто из вас прав.


27-01-2008 07:30
Здраствуйте, Антон Грирорьев...

Вы писали:
>Достоинства автоматов заключаются в том, что их код универсален, а грамматика задаётся таблицей >переходов, которая может находиться, например, во внешнем файле. Поэтому, если грамматика может меняться, >автомат не обязательно перекомпилировать. Таким образом, автоматы полезны там, где грамматика может >меняться или где используется много разных грамматик. Но по производительности МП-автомат показывает не >очень хорошие результаты из-за возможности захода в тупиковые ветви и последующего возврата из них.

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

В ваш ответ вкралась небольшая неточность, которая может ввести в заблуждение читателей...
Сравнивая МП автоматы, построеные на основе LR-грамматик, и метод рекурсивного спуска, который применется для LL грамматик, можно выделить следующие отличия:
Главным достоинством метода рекурсивно спуска является его понятность и простота, так для каждого правила существуется специальная функция-обработчик. К минусам же этого метода относят, то что он не может быть применён для грамматик содержащих левую рекурсию (<A> ::= <A> ',' a) - приходиться от неё избавляться, и то что имменно он заходит в тупиковые ветки и возврщается из них, за счёт чего и показывает более низкое быстродействие.

МП автомат, же работае строго по таблице переходов и в кажом своём состоянии по входному сиволу легко определяет что ему делать дальше - никаких возвратов по входному потоку он не производит.Минусами же его является, то что построение таблицы переходов очень сложный процесс (хотя существуют программы, например yacc которые строят ей автоматичски) и то что при изменении грамматики приходиться практически с нуля расставлять скмантические действия.

Подводя итог:
МП автомат:
Достоинства:
1) Высокое быстродействие
2) Унифицированный алгоритм работы автомата

Недостатки:
1) Сложность построения таблицы переходов
2) Трудоёмкость обновления семантических действий при изменении грамматики

Метод рекурсивного спуска:
Достоинства:
1) Наглядность и простота алгоритма

Недостатки:
1) Более низкая скорость из-за захода и возврата в тупиковые ветки

P.S. Все выше сказанное основывается на моём и книге "Компиляторы. Принципы, технологии, инструменты" Альфред Ахо, Рави Сети, Джеффри Ульман


09-09-2007 18:13
Прекрасная статья + прекрасный пример.
5 балов!

Мне потребовалось написать свой анализатор формул, но Вы мне сэкономили уйму времени предоставив каркас,хотя работы ещё много, но фундамент уже есть. Отлично!


16-03-2007 15:56
Отличная статья, спасибо за информацию.
Как раз решаю вопрос про калькулятор.


Самое ценное в интернете - это знания и опыт людей.
 Comp


09-03-2007 06:43
сообщение от автора материала
Прошу больше не задавать мне здесь вопросы типа того, как сделать функцию с двумя аргументами. В статье я как мог подробно изложил и принципы формирования грамматики, и метод написания кода на основании такой грамматики. Если вы не хотите со всем этим разбираться, то это, конечно же, ваше право, но и мне тоже просто неинтересно писать отдельный код под каждую лишнюю запятую.


03-03-2007 01:02
Я читал. А как это написать в Delphi? Я несколько раз пытался, но у меня ничего не получилось...


02-03-2007 23:04
сообщение от автора материала
Напишите, пожалуйста, как ввести функцию с 2 аргументами.

Читайте комментарии. Уже писал на два поста ниже.


02-03-2007 21:55
Напишите, пожалуйста, как ввести функцию с 2 аргументами.


02-03-2007 02:35
сообщение от автора материала
Единственное, хотелось бы прочитать какое место такой "синтаксический анализ выражений" занимает
среди других методов: польская запись, конечный автомат и что там есть еще из наиболее употребительного в "разборе" математических выражений.
Какие у него достоинства и недостатки, чем он лучше других? Что говорит "мировой опыт" по этим вопросам? Если возможно, конечно.


Хоть и с большим опозданием, но отвечаю :)

Наиболее общая форма записи грамматических правил имеет вид a ::= b, где a и b - произвольные цепочки из терминальных и нетерминальных символов. Единственное ограничение - цепочка a не должна быть пустой. Существуют следующие частные случаи:

1. Контекстно-зависимые грамматики. Правила в них имеют вид a<X>b ::= acb, где a, b и c - произвольные цепочки, <X> - некоторый нетерминальный символ. Суть в том, что <X> может заменяться на c только в том случае, когда вокруг стоят a и b, т.е. в определённом конексте.

2. Контекстно-свободные грамматики. Парвила в них имеют вид <X> ::= a, т.е. в левой части стоит единственный нетерминальный символ, который может быть заменён цепочкой a в любом контексте.

3. Автоматные грамматики - контекстно-свободные грамматики без рекурсии.

Конечные автоматы применимы только для разбора автоматных грамматик. В нашем же случае грамматики являются автоматными только до тех пор, пока мы не ввели скобки. Вместе со скобками появляется рекурсия, и грамматика превращается в контекстно-свободную, поэтому конечный автомат для неё уже неприменим. Тут нужен МП-автомат - автомат с магазинной памятью. Это примерно то же самое, что и конечный автомат, но снабжённый стеком, и направление переходов в нем определяется не только очередным символом, но и элементом на вершине стека.

Достоинства автоматов заключаются в том, что их код универсален, а грамматика задаётся таблицей переходов, которая может находиться, например, во внешнем файле. Поэтому, если грамматика может меняться, автомат не обязательно перекомпилировать. Таким образом, автоматы полезны там, где грамматика может меняться или где используется много разных грамматик. Но по производительности МП-автомат показывает не очень хорошие результаты из-за возможности захода в тупиковые ветви и последующего возврата из них.

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

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

Польская запись может оказаться полезной там, где нужно промежуточное представление выражения, удобное для анализа - например, при построении компилятора. Или, например, код вычисления выражения для стековой машины (например, для JVM) - это, по сути дела, тоже польская запись. Но простой интерпретатор, рассмотренный в статье, в этом, повторяю, не нуждается.


30-11-2006 07:53
сообщение от автора материала
Как ввести в анализатор фугкции с двумя аргументами? Например, Log(a,b).

Очень просто - переопределить <Function> так:

<Function> ::= <FuncName> '(' <MathExpr> [',' <MathExpr>] ')'

И ещё один вопрос как добавить функцию модуля?  Чтобы пользователь вводил знак '|', далее аргумент, далее сгова '|'. Например, |x-12|.

Ввести в <Base> ещё одну альтернативу - '|' <MathExpr> '|'

Материал ОЧЕНЬ помог в написании курсовой

Каким именно образом помог? Если бы вы разобрались с материалом, такие лёгкие вопросы (особенно с модулем) не вызвали бы у вас ни малейших затруднений. А так - есть подозрение, что вся "помощь" заключалась в простом копировании текста и/или кода.


30-11-2006 07:41
Здравствуйте Антон. Ответьте, пожалуйста, на вопрос. Как ввести в анализатор фугкции с двумя аргументами? Например, Log(a,b). И ещё один вопрос как добавить функцию модуля?  Чтобы пользователь вводил знак '|', далее аргумент, далее сгова '|'. Например, |x-12|.


30-11-2006 07:20
Материал ОЧЕНЬ помог в написании курсовой


04-11-2006 06:13
Достаточно сильно помогло в понимании этой проблеммы


21-03-2006 16:44
Хорошая статья.


01-12-2005 08:29
Давненько не прикасался к паскалю, однако, статья так написана, что разобрался без проблем. "Доходчиво излагаете , товарищ." :-) Спасибо.

Единственное, хотелось бы прочитать какое место такой "синтаксический анализ выражений" занимает
среди других методов: польская запись, конечный автомат и что там есть еще из наиболее употребительного в "разборе" математических выражений.
Какие у него достоинства и недостатки, чем он лучше других? Что говорит "мировой опыт" по этим вопросам? Если возможно, конечно.


20-06-2005 06:10
сообщение от автора материала
Антон, а какой программой вы рисуете эти рельсовые диаграммы?

Сначала нарисовал в MS Visio, потом экпоритровал в BMP, потом в Paint'е подправлял :)


20-06-2005 06:05
Антон, а какой программой вы рисуете эти рельсовые диаграммы?


29-04-2005 04:48
сообщение от автора материала
Не вижу я, куда и зачем тут можно прикрутить польскую нотацию. Это уже совсем другая тема, в статью она просто не вписывается.


24-04-2005 05:14
Извиняюсь, не подумал о шрифте:

обычная запись:   A+B      
ПОЛИЗ:   AB+

или  

обычная запись:   A+5*C
ПОЛИЗ:   A5C*+

или

обычная запись:   (A+B)*(C+2)+F
ПОЛИЗ:   AB+C2+*F+


24-04-2005 05:10
Статья отличная. Можно было ещё упомянуть о ПОЛИЗ (Польская инверсная запись) арифметических выражений.
Например:      
------------------------------
| обычная запись |    ПОЛИЗ    |
|----------------+-------------|
|     A+B        |  AB+        |
|    A+5*C       |  A5C*+      |
| (A+B)*(C+2)+F  |  AB+C2+*F+  |
------------------------------
Если не ошибаюсь, это используется(использовалось) при построении компиляторов и реальных калькуляторов.


Добавьте свое cообщение

Вашe имя:  [Войти]
Ваш адрес (e-mail):На Королевстве все адреса защищаются от спам-роботов
контрольный вопрос:
Зимой — белый, летом — серый. Кто?
в качестве ответа на вопрос или загадку следует давать только одно слово в именительном падеже и именно в такой форме, как оно используется в оригинале.
Надоело отвечать на странные вопросы? Зарегистрируйтесь на сайте.

Оценка содержания
 
Содержит полезные и(или) интересные сведения
 
Ничего особенно нового и интересного
 
Написано неверно (обязательно укажите почему)


Оценка стиля изложения
 
Все понятно, материал читается легко
 
Есть неясности в изложении
 
Непонятно написано, трудно читается

Текст:
Жирный шрифт  Наклонный шрифт  Подчеркнутый шрифт  Выравнивание по центру  Список  Заголовок  Разделительная линия  Код  Маленький шрифт  Крупный шрифт  Цитирование блока текста  Строчное цитирование
  • вопрос Круглого стола № XXX

  • вопрос № YYY в тесте № XXX Рыцарской Квинтаны

  • сообщение № YYY в теме № XXX Базарной площади
  • обсуждение темы № YYY Базарной площади
  •  
     Правила оформления сообщений на Королевстве
      
    Время на сайте: GMT минус 5 часов

    Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter.
    Функция может не работать в некоторых версиях броузеров.

    Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
    Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

     
    © При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
    Все используемые на сайте торговые марки являются собственностью их производителей.

    Яндекс цитирования