Действительно ли лексеры и парсеры в теории отличаются друг от друга
Кажется модным ненавидеть регулярные выражения: ужас кодирования , еще одно сообщение в блоге .
Однако популярные инструменты, основанные на лексизме: pygments , geshi или prettify - все используют регулярные выражения. Кажется, они лекс что-нибудь ...
Когда достаточно лексизма, когда вам нужен EBNF?
Кто-нибудь использовал токены, созданные этими лексерами, с помощью генераторов синтаксического анализатора bison или antlr?
Ответы:
Что общего у парсеров и лексеров:
Они читают символы некоторого алфавита из своего ввода.
Они анализируют эти символы и пытаются сопоставить их с грамматикой языка, который они понимают.
Они придают семантику (смысл) языковым частям, которые они находят.
*
,==
,<=
,^
будут классифицироваться как «оператор» токен C / C ++ лексером.[number][operator][number]
,[id][operator][id]
,[id][operator][number][operator][number]
будут классифицироваться как «выражение» нетерминалом по C / C ++ парсера.Они могут придавать дополнительное значение (данные) распознаваемым элементам.
Все они выдают на выходе правильные предложения языка, который они распознают.
[TXT][TAG][TAG][TXT][TAG][TXT]...
.Как видите, парсеры и токенизаторы имеют много общего. Один синтаксический анализатор может быть токенайзером для другого синтаксического анализатора, который считывает свои входные токены как символы из своего собственного алфавита (токены являются просто символами некоторого алфавита) так же, как предложения из одного языка могут быть буквенными символами некоторого другого, более высокого уровня язык. Например, если
*
и-
являются символами алфавитаM
(как «символы азбуки Морзе»), то вы можете создать синтаксический анализатор, который распознает строки этих точек и линий как буквы, закодированные в коде Морзе. Предложения на языке «азбуки Морзе» могут быть токенами для какого-то другого парсера, для которого эти токеныявляются атомными символами своего языка (например, язык «английских слов»). И эти «английские слова» могут быть токенами (символами алфавита) для некоего парсера более высокого уровня, который понимает язык «английских предложений». И все эти языки отличаются только сложностью грамматики . Ничего более.Так что же это за «грамматические уровни Хомского»? Нуам Хомский разделил грамматику на четыре уровня в зависимости от их сложности:
Уровень 3: Обычные грамматики
Они используют регулярные выражения, то есть, они могут состоять только из символов алфавита (a
,b
), их конкатенации (ab
,aba
,bbb
ETD.), Или альтернативные варианты (напримерa|b
).Они могут быть реализованы как конечные автоматы (FSA), такие как NFA (недетерминированный конечный автомат) или лучший DFA (детерминированный конечный автомат).
Обычные грамматики не могут работать с вложенным синтаксисом , например, правильно вложенными / совпавшими круглыми скобками
(()()(()()))
, вложенными тегами HTML / BBcode, вложенными блоками и т. Д. Это потому, что автоматы состояний должны иметь бесконечно много состояний, чтобы обрабатывать бесконечно много уровней вложенности.Уровень 2: контекстно-свободные грамматики
Они могут иметь вложенные, рекурсивные, самоподобные ветви в своих синтаксических деревьях, поэтому они могут хорошо работать с вложенными структурами.Их можно реализовать как конечный автомат со стеком. Этот стек используется для представления уровня вложенности синтаксиса. На практике они обычно реализуются как анализатор рекурсивного спуска сверху вниз, который использует стек вызовов машинных процедур для отслеживания уровня вложенности и использует рекурсивно вызываемые процедуры / функции для каждого нетерминального символа в своем синтаксисе.
Но они не могут справиться с контекстно-зависимым синтаксисом. Например, когда у вас есть выражение,
x+3
и в одном контексте этоx
может быть имя переменной, а в другом контексте это может быть имя функции и т. Д.Уровень 1: контекстно-зависимая грамматика
Уровень 0: Неограниченные грамматики
Также называются рекурсивно перечислимыми грамматиками.
источник
STMT_END
в вашем синтаксисе (для синтаксического анализатора) для обозначения конца инструкций. Теперь вы можете иметь связанный с ним токен, сгенерированный лексером. Но вы можете изменить фактическую лексему, которую он обозначает. Например. Вы можете определитьSTMT_END
как;
иметь C / C ++ - как исходный код. Или вы можете определить его так,end
чтобы он был похож на стиль Паскаля. Или вы можете определить его как'\n'
конец инструкции с конца строки, как в Python. Но синтаксис инструкции (и синтаксический анализатор) остается неизменным :-) Необходимо изменить только лексер.Да, они очень разные как в теории, так и в реализации.
Лексеры используются для распознавания «слов», составляющих языковые элементы, потому что структура таких слов, как правило, проста. Регулярные выражения очень хорошо справляются с этой более простой структурой, и для реализации лексеров используются очень высокопроизводительные механизмы сопоставления регулярных выражений.
Парсеры используются для распознавания «структуры» языковых фраз. Такая структура обычно намного превосходит то, что могут распознавать «регулярные выражения», поэтому для извлечения такой структуры нужны «контекстно-зависимые» синтаксические анализаторы. Контекстно-зависимые парсеры сложны в построении, поэтому компромиссом для инженеров является использование «контекстно-свободных» грамматик и добавление хаков в парсеры («таблицы символов» и т. Д.) Для обработки контекстно-зависимой части.
Ни лексинг, ни технология синтаксического анализа вряд ли скоро исчезнут.
Они могут быть объединены, решив использовать технологию «разбора» для распознавания «слов», как это в настоящее время исследуют так называемые анализаторы GLR без сканирования. Это требует затрат времени выполнения, поскольку вы применяете более общий механизм для решения часто не нуждающейся проблемы, и обычно вы платите за это накладными расходами. Там, где у вас много свободных циклов, эти накладные расходы могут не иметь значения. Если вы обрабатываете много текста, накладные расходы имеют значение, и классические парсеры регулярных выражений будут продолжать использоваться.
источник
EBNF действительно не добавляет много силы грамматике. Это просто удобное / сокращенное обозначение / «синтаксический сахар» по сравнению со стандартными грамматическими правилами Хомского в нормальной форме (CNF). Например, альтернатива EBNF:
Вы можете достичь в CNF, перечислив каждую альтернативную продукцию отдельно:
Необязательный элемент от EBNF:
Вы можете достичь в CNF, используя пустое произведение, то есть то, которое можно заменить пустой строкой (здесь обозначается просто пустое производство; другие используют эпсилон или лямбду или скрещенный круг):
Производство в форме, подобной последней
B
, называется «стиранием», поскольку оно может стереть все, что обозначает в других производствах (создать пустую строку вместо чего-то еще).Повторение нуля или более от EBNF:
вы можете обтанировать, используя рекурсивное производство, то есть то, которое встраивается где-то в него Это можно сделать двумя способами. Первый - это левая рекурсия (чего обычно следует избегать, потому что анализаторы нисходящего рекурсивного спуска не могут ее проанализировать):
Зная, что он генерирует только пустую строку (в конечном итоге), за которой следует ноль или более
A
s, эту же строку ( но не тот же язык! ) Можно выразить с помощью правой рекурсии :И когда дело доходит до
+
одного или нескольких повторений от ЕБНФ:это можно сделать, выделив один
A
и использовав,*
как и раньше:который вы можете выразить в CNF как таковой (здесь я использую правильную рекурсию; попробуйте самостоятельно найти другую в качестве упражнения):
Зная это, теперь вы, вероятно, можете распознать грамматику для регулярного выражения (то есть регулярной грамматики ) как грамматику, которая может быть выражена в единственном произведении EBNF, состоящем только из терминальных символов. В более общем смысле, вы можете распознать обычные грамматики, когда видите произведения, подобные этим:
То есть, используя только пустые строки, терминальные символы, простые нетерминалы для подстановок и изменений состояния, и используя рекурсию только для достижения повторения (итерация, которая является просто линейной рекурсией - та, которая не ветвится как дерево). Ничего более сложного, кроме этого, вы уверены, что это обычный синтаксис, и вы можете использовать только лексер для этого.
Но когда ваш синтаксис использует рекурсию нетривиальным способом, для создания древовидных, самоподобных, вложенных структур, как показано ниже:
тогда вы можете легко увидеть, что это невозможно сделать с помощью регулярного выражения, потому что вы не можете никоим образом разрешить его в одну единицу EBNF; Вы будете в конечном итоге заменять на
S
неопределенное время, что всегда будет добавлять другиеa
s иb
s с обеих сторон. Лексеры (точнее: конечные автоматы, используемые лексерами) не могут сосчитать до произвольного числа (они конечны, помните?), Поэтому они не знают, сколько былоa
s, чтобы сопоставить их равномерно с таким количествомb
s. Такие грамматики называются контекстно-свободными грамматиками (по крайней мере), и для них требуется синтаксический анализатор.Не зависящие от контекста грамматики хорошо разбираются, поэтому они широко используются для описания синтаксиса языков программирования. Но это еще не все. Иногда требуется более общая грамматика - когда у вас есть много вещей, чтобы сосчитать одновременно, независимо. Например, когда вы хотите описать язык, в котором можно использовать круглые скобки и квадратные скобки с чередованием, но они должны быть правильно спарены друг с другом (фигурные скобки с круглыми скобками). Этот вид грамматики называется контекстно-зависимым . Вы можете распознать его по тому, что у него более одного символа слева (перед стрелкой). Например:
Вы можете рассматривать эти дополнительные символы слева как «контекст» для применения правила. Там могут быть некоторые предпосылки, постусловия и т.д. Например, указанное правило будет заменить
R
наS
, но только тогда , когда это междуA
иB
, оставив тех ,A
иB
себя неизменным. Этот вид синтаксиса действительно трудно разобрать, потому что ему нужна полноценная машина Тьюринга. Это совсем другая история, поэтому я закончу здесь.источник
Чтобы ответить на вопрос в том виде, в котором он был задан (без чрезмерного повторения того, что появляется в других ответах)
Лексеры и парсеры не сильно отличаются, как предполагает принятый ответ. Оба основаны на простых языковых формализмах: обычные языки для лексеров и, почти всегда, контекстно-свободные (CF) языки для синтаксических анализаторов. Обе они связаны с довольно простыми вычислительными моделями, автоматом конечных состояний и автоматом стека. Регулярные языки - это особый случай контекстно-свободных языков, так что лексеры могут быть созданы с использованием несколько более сложной технологии CF. Но это не очень хорошая идея, по крайней мере, по двум причинам.
Фундаментальный момент в программировании заключается в том, что системный компонент должен быть оснащен самой подходящей технологией, чтобы его было легко создавать, понимать и поддерживать. Технология не должна быть излишней (с использованием методов, намного более сложных и дорогостоящих, чем необходимо), и не должна быть на пределе своих возможностей, поэтому требуются технические искажения для достижения желаемой цели.
Вот почему «Кажется модным ненавидеть регулярные выражения». Хотя они могут многое сделать, им иногда требуется очень нечитаемое кодирование для достижения этого, не говоря уже о том, что различные расширения и ограничения в реализации несколько снижают их теоретическую простоту. Обычно лексеры этого не делают и обычно представляют собой простую, эффективную и подходящую технологию для анализа токена. Использование парсера CF для токена было бы излишним, хотя это возможно.
Другая причина не использовать формализм CF для лексеров заключается в том, что может возникнуть соблазн использовать всю мощь CF. Но это может вызвать серьезные проблемы с чтением программ.
По сути, большая часть структуры программного текста, из которой извлекается значение, представляет собой древовидную структуру. Он выражает, как предложение синтаксического анализа (программа) генерируется из правил синтаксиса. Семантика получена композиционными методами (гомоморфизм для математически ориентированных) из способа составления синтаксических правил для построения дерева разбора. Следовательно, древовидная структура имеет важное значение. Тот факт, что токены отождествляются с лексером на основе регулярного набора, не меняет ситуацию, потому что CF, составленный из регулярного, все еще дает CF (я говорю очень свободно о регулярных преобразователях, которые преобразуют поток символов в поток токенов).
Однако CF, составленный из CF (через преобразователи CF ... извините за математику), не обязательно дает CF, и может сделать вещи более общими, но менее понятными на практике. Таким образом, CF не подходит для лексеров, хотя его можно использовать.
Одно из основных различий между обычным и CF состоит в том, что обычные языки (и преобразователи) очень хорошо сочетаются практически с любым формализмом различными способами, в то время как языки CF (и преобразователи) этого не делают, даже с самими собой (за некоторыми исключениями).
(Обратите внимание, что обычные преобразователи могут иметь другое применение, например, формализацию некоторых методов обработки синтаксических ошибок.)
BNF - это просто особый синтаксис для представления грамматик CF.
EBNF является синтаксическим сахаром для BNF , использующим средства регулярного обозначения, чтобы дать более краткую версию грамматик BNF. Он всегда может быть преобразован в эквивалентный чистый БНФ.
Тем не менее, регулярные обозначения часто используются в EBNF только для того, чтобы подчеркнуть эти части синтаксиса, которые соответствуют структуре лексических элементов, и должны быть распознаны с помощью лексера, тогда как остальные должны быть скорее представлены в прямой BNF. Но это не абсолютное правило.
Подводя итог, можно сказать, что более простая структура токена лучше анализируется с помощью более простой технологии обычных языков, в то время как древовидная структура языка (синтаксиса программы) лучше обрабатывается грамматиками CF.
Я бы предложил также посмотреть на ответ AHR .
Но это оставляет открытым вопрос: почему деревья?
Деревья являются хорошей основой для определения синтаксиса, потому что
они дают простую структуру тексту
Есть очень удобно связывать семантику с текстом на основе этой структуры с помощью математически хорошо понятной технологии (композиционность через гомоморфизмы), как указано выше. Это фундаментальный алгебраический инструмент для определения семантики математических формализмов.
Следовательно, это хорошее промежуточное представление, о чем свидетельствует успех абстрактных синтаксических деревьев (AST). Обратите внимание, что AST часто отличаются от дерева разбора, потому что технология синтаксического анализа, используемая многими профессионалами (такими как LL или LR), применяется только к подмножеству грамматик CF, таким образом, вызывая грамматические искажения, которые впоследствии исправляются в AST. Этого можно избежать с помощью более общей технологии синтаксического анализа (основанной на динамическом программировании), которая принимает любую грамматику CF.
Утверждение о том, что языки программирования являются контекстно-зависимыми (CS), а не CF, являются произвольными и спорными.
Проблема в том, что разделение синтаксиса и семантики является произвольным. Проверка объявлений или соглашения о типе может рассматриваться как часть синтаксиса или как часть семантики. То же самое относится и к гендерному и числовому соглашению на естественных языках. Но существуют естественные языки, где множественное число зависит от фактического семантического значения слов, так что оно не вписывается в синтаксис.
Многие определения языков программирования в денотационной семантике помещают объявления и проверку типов в семантику. Заявление Ира Бакстера о том, что парсеры CF взламываются, чтобы получить контекстную чувствительность, требуемую синтаксисом, в лучшем случае - произвольный взгляд на ситуацию. Это может быть организовано как взломать в некоторых компиляторах, но это не обязательно.
Также дело не только в том, что парсеры CS (в том смысле, в каком они здесь используются в других ответах) сложны и менее эффективны. Они также неадекватны для того, чтобы явно выразить вид контекстной чувствительности, который может потребоваться. И они, естественно, не создают синтаксическую структуру (такую как деревья разбора), которая удобна для получения семантики программы, то есть для генерации скомпилированного кода.
источник
Существует ряд причин, по которым часть анализа компилятора обычно разделяется на фазы лексического анализа и синтаксического анализа (синтаксического анализа).
resource___ Compilers (2nd Edition), написанный Альфредом В. Або Колумбийским университетом Моника С. Лэм Стэнфордский университет Рави Сетхи Авая Джеффри Д. Уллман Стэнфордский университет
источник