лексеры против парсеров

Действительно ли лексеры и парсеры различны в теории?

Кажется модным ненавидеть регулярные выражения: ужас кодирования , еще одно сообщение в блоге .

Однако популярные инструменты на основе лексики: pygments , geshi или prettify , все используют регулярные выражения. Кажется, что они лексики …

Когда достаточно lexing, когда вам нужен EBNF?

Кто-нибудь использовал токены, созданные этими лексерами, с генераторами парсера или бинда?

Что общего у парсеров и лексеров:

  1. Они читают символы какого-либо алфавита с их ввода.

    • Подсказка: алфавит не обязательно должен иметь буквы. Но это должно быть символов, которые являются атомарными для языка, понимаемого парсером / лексером.
    • Символы для lexer: символы ASCII.
    • Символы для синтаксического анализатора: конкретные маркеры, которые являются терминальными символами их грамматики.
  2. Они анализируют эти символы и пытаются сопоставить их с грамматикой языка, который они понимают.

    • Вот где обычно лежит реальная разница. См. Ниже.
    • Грамматика понимается лексерами: регулярная грамматика (уровень 3 Хомского).
    • Грамматика понимается парсерами: контекстно-свободная грамматика (уровень 2 Хомского).
  3. Они придают семантике (значению) языковые fragmentы, которые они находят.

    • Лексеры придают значение, classифицируя лексемы (строки символов из ввода) в качестве конкретных токенов . Например, все эти лексемы: * , == , <= , ^ будут classифицированы как «операторный» токен лексикой C / C ++.
    • Parsers присваивают значение, classифицируя строки токенов из ввода (предложений) как конкретные нетерминалы и строя дерево parsingа . Например, все эти токенныи строки: [number][operator][number] , [id][operator][id] , [id][operator][number][operator][number] будет classифицироваться как «выражение» нетерминал синтаксический анализатор C / C ++.
  4. Они могут прикрепить некоторые дополнительные значения (данные) к признанным элементам.

    • Когда лексер распознает последовательность символов, составляющую правильное число, он может преобразовать его в двоичное значение и сохранить с помощью токена «число».
    • Аналогично, когда парсер распознает выражение, он может вычислить его значение и сохранить с помощью «выражения» узла дерева синтаксиса.
  5. Все они производят на своем выходе правильные предложения распознаваемого языка.

    • Лексеры производят токены , которые являются предложениями обычного языка, который они распознают. Каждый токен может иметь внутренний синтаксис (хотя уровень 3, а не уровень 2), но это не имеет значения для выходных данных и для тех, которые их читают.
    • Парсеры создают синтаксические деревья , которые представляют собой предложения предложений контекстно-свободного языка, который они распознают. Обычно это всего лишь одно большое дерево для всего документа / исходного файла, потому что весь документ / исходный файл является для них подходящим предложением . Но нет причин, по которым парсер не мог создать серию синтаксических деревьев на своем выходе. Например, это может быть парсер, который распознает tags SGML, прикрепленные к текстовому тексту. Поэтому он будет документировать документ SGML в серии токенов: [TXT][TAG][TAG][TXT][TAG][TXT]...

Как вы можете видеть, синтаксические анализаторы и токенизаторы имеют много общего. Один парсер может быть токенизатором для другого синтаксического анализатора, который считывает свои входные токены в виде символов из своего собственного алфавита (токены - это просто символы некоторого алфавита) так же, как предложения с одного языка могут быть алфавитными символами какого-либо другого, более высокого уровня язык. Например, если * и - являются символами алфавита M (как «символы кода Морзе»), вы можете создать парсер, который распознает строки этих точек и строк как буквы, закодированные в коде Морзе. Предложения на языке «Код Морзе» могут быть токенами для другого синтаксического анализатора, для которого эти токены являются атомными символами его языка (например, язык «Английские слова»). И эти «английские слова» могут быть токенами (символами алфавита) для некоторого более сильного анализатора, который понимает «английский язык». И все эти языки отличаются только сложностью грамматики . Больше ничего.

Так что же все эти «грамматические уровни Хомского»? Ну, Ноам Хомский classифицировал грамматики на четыре уровня в зависимости от их сложности:

  • Уровень 3: Регулярные грамматики

    Они используют регулярные выражения, то есть они могут состоять только из символов алфавита ( a , b ), их конкатенаций ( ab , aba , bbb etd.) Или альтернатив (например, a|b ).
    Они могут быть реализованы как автоматы с конечным состоянием (FSA), такие как NFA (недетерминированный конечный автомат) или лучше DFA (детерминированный конечный автомат).
    Регулярные грамматики не могут обрабатывать вложенные синтаксисы , например, правильно вложенные / совпадающие скобки (()()(()())) , вложенные tags HTML / BBcode, вложенные блоки и т. Д. Это связано с тем, что автоматы состояния должны иметь дело с ним имеют бесконечно много состояний для обработки бесконечно много уровней гнездования.

  • Уровень 2: Контекстно-свободные грамматики

    Они могут иметь вложенные, рекурсивные, похожие на себя ветви в своих синтаксических деревьях, поэтому они могут хорошо обрабатывать вложенные структуры.
    Они могут быть реализованы как государственный автомат со стеком. Этот стек используется для представления уровня вложенности синтаксиса. На практике они обычно реализуются как парсер с наименьшим, рекурсивным спусками, который использует стек вызовов процедуры компьютера для отслеживания уровня вложенности и использует рекурсивно называемые процедуры / функции для каждого нетерминального символа в своем синтаксисе.
    Но они не могут обрабатывать контекстно-зависимый синтаксис. Например, когда у вас есть выражение x+3 и в одном контексте это x может быть именем переменной, а в другом контексте это может быть имя функции и т. Д.

  • Уровень 1: Контекстно-зависимые грамматики

  • Уровень 0: Неограниченные грамматики
    Также называются «грамматики фазовой структуры».

Да, они очень разные в теории и в реализации.

Лексеры используются для распознавания «слов», составляющих языковые элементы, потому что структура таких слов обычно проста. Регулярные выражения чрезвычайно полезны при обработке этой более простой структуры, и существуют очень высокопроизводительные механизмы соответствия регулярному выражению, используемые для реализации лексеров.

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

Ни технология лексинга, ни синтаксический анализ, скорее всего, скоро исчезнут.

Они могут быть унифицированы, решив использовать технологию «синтаксического анализа» для распознавания «слов», как это в настоящее время изучается так называемыми сканерными анализаторами GLR. У этого есть затраты времени исполнения, поскольку вы применяете более общий механизм к тому, что часто является проблемой, которая ему не нужна, и обычно вы платите за это накладные расходы. Там, где у вас много бесплатных циклов, эти накладные расходы могут не иметь значения. Если вы обрабатываете много текста, тогда накладные расходы имеют значение, и classические анализаторы регулярных выражений будут по-прежнему использоваться.

Когда достаточно lexing, когда вам нужен EBNF?

EBNF действительно не добавляет много к силе грамматик. Это просто удобная / короткая нотация / «синтаксический сахар» по стандартным правилам грамматики обычной формы Чомского. Например, альтернатива EBNF:

 S --> A | B 

вы можете достичь в CNF, просто перечислив каждую альтернативную продукцию отдельно:

 S --> A // `S` can be `A`, S --> B // or it can be `B`. 

Необязательный элемент из EBNF:

 S --> X? 

вы можете достичь в CNF, используя нулевую продукцию, то есть ту, которая может быть заменена пустой строкой (здесь обозначается только пустая постановка, другие используют epsilon или lambda или скрещенный круг):

 S --> B // `S` can be `B`, B --> X // and `B` can be just `X`, B --> // or it can be empty. 

Произведение в форме, подобной предыдущей B выше, называется «стиранием», потому что оно может стирать все, что он обозначает в других постановках (произведите пустую строку вместо чего-то другого).

Больше или больше повторений от EBNF:

 S --> A* 

вы можете obtan, используя рекурсивное производство, то есть тот, который внедряется где-то в нем. Это можно сделать двумя способами. Первая из них оставлена ​​рекурсией (чего обычно следует избегать, поскольку синтаксические анализаторы «Сверху вниз» не могут ее разобрать):

 S --> SA // `S` is just itself ended with `A` (which can be done many times), S --> // or it can begin with empty-string, which stops the recursion. 

Зная, что он генерирует только пустую строку (в конечном счете), за которой следует ноль или более A s, одна и та же строка ( но не тот же язык! ) Может быть выражена с помощью правильной рекурсии :

 S --> AS // `S` can be `A` followed by itself (which can be done many times), S --> // or it can be just empty-string end, which stops the recursion. 

И когда дело доходит до + для одного или нескольких повторений от EBNF:

 S --> A+ 

это можно сделать, разложив один A и используя * как и раньше:

 S --> AA* 

который вы можете выразить в CNF как таковой (я использую здесь правильную рекурсию, попытаюсь выяснить другую в качестве упражнения):

 S --> AS // `S` can be one `A` followed by `S` (which stands for more `A`s), S --> A // or it could be just one single `A`. 

Зная это, теперь вы можете, вероятно, распознать грамматику для регулярного выражения (т. Е. Регулярную грамматику ) как та, которая может быть выражена в одном выпуске EBNF, состоящем только из терминальных символов. В более общем плане вы можете распознавать регулярные грамматики, когда вы видите похожие на них произведения:

 A --> // Empty (nullable) production (AKA erasure). B --> x // Single terminal symbol. C --> y D // Simple state change from `C` to `D` when seeing input `y`. E --> F z // Simple state change from `E` to `F` when seeing input `z`. G --> G u // Left recursion. H --> v H // Right recursion. 

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

Но когда ваш синтаксис использует рекурсию нетривиальным способом, для создания древовидных, самоподобных вложенных структур, таких как следующий:

 S --> a S b // `S` can be itself "parenthesized" by `a` and `b` on both sides. S --> // or it could be (ultimately) empty, which ends recursion. 

то вы можете легко увидеть, что это невозможно сделать с регулярным выражением, потому что вы не можете разрешить его в одном производстве EBNF каким-либо образом; вы закончите тем, что замените S неопределенный срок, что всегда будет добавлять другие s и b s с обеих сторон. Лексеры (точнее говоря: автоматы конечных состояний, используемые лексерами) не могут рассчитывать на произвольное число (они конечны, помните?), Поэтому они не знают, сколько a них должно было бы равномерно их сопоставлять с таким количеством b . Грамматики, подобные этому, называются контекстно-свободными грамматиками (по крайней мере), и им нужен парсер.

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

 ARB --> ASB 

Вы можете представить эти дополнительные символы слева как «контекст» для применения правила. Могут быть некоторые предпосылки, постусловия и т. Д. Например, вышеприведенное правило заменит R на S , но только тогда, когда оно находится между A и B , оставив эти A и B без изменений. Такой синтаксис действительно трудно разобрать, потому что ему нужна полномасштабная машина Тьюринга. Это совсем другая история, поэтому я закончу здесь.

Чтобы ответить на заданный вопрос (не повторяя излишне то, что появляется в других ответах)

Лексеры и парсеры не очень разные, как это принято в принятом ответе. Оба они основаны на простых языковых формализмах: регулярных языках для лексеров и почти всегда, контекстно-свободных (CF) языках для парсеров. Оба они связаны с довольно простыми вычислительными моделями, автоматом конечного состояния и автоматом push-down stack. Регулярные языки являются особым случаем контекстно-свободных языков, поэтому лексеры могут быть созданы с несколько более сложной технологией CF. Но это не очень хорошая идея по крайней мере по двум причинам.

Основополагающим моментом в программировании является то, что системный компонент должен быть построен с наиболее подходящей технологией, поэтому его легко производить, понимать и поддерживать. Технология не должна быть чрезмерной (используя методы, намного более сложные и дорогостоящие, чем необходимо), а также не должно быть предела ее мощности, что требует технических искажений для достижения желаемой цели.

Вот почему «Кажется модным ненавидеть регулярные выражения». Хотя они могут многое сделать, для их достижения иногда требуется очень нечитаемое кодирование, не говоря уже о том, что различные расширения и ограничения в реализации несколько уменьшают их теоретическую простоту. Лексеры обычно этого не делают, и обычно это простая, эффективная и подходящая технология для анализа токена. Использование парсеров CF для токена было бы излишним, хотя это возможно.

Другая причина не использовать формализм CF для лексеров заключается в том, что тогда может возникнуть соблазн использовать полную мощность CF. Но это может привести к возникновению структурных проблем, связанных с чтением программ.

По сути, большая часть структуры текста программы, из которой извлекается смысл, является древовидной структурой. Он выражает, как предложение (программа) синтаксического анализа генерируется из правил синтаксиса. Семантика выводится композиционными методами (гомоморфизм для математически ориентированных) из того, как составлены синтаксические правила для построения дерева синтаксического анализа. Следовательно, древовидная структура имеет важное значение. Тот факт, что маркеры идентифицированы с использованием стандартного набора лексера, не изменяет ситуацию, потому что CF, составленный с регулярным, все еще дает CF (я говорю очень свободно о регулярных преобразователях, которые преобразуют stream символов в stream токена).

Однако CF, состоящий из CF (через CF-преобразователи … извините за математику), не обязательно дает CF, и может сделать вещи более общими, но менее приемлемыми на практике. Таким образом, CF не является подходящим инструментом для лексеров, хотя его можно использовать.

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

(Обратите внимание, что обычные преобразователи могут использовать другие, такие как формализация некоторых методов обработки синтаксических ошибок).

BNF – это всего лишь особый синтаксис для представления CF-грамматик.

EBNF является синтаксическим сахаром для BNF , используя средства регулярной нотации, чтобы дать термерную версию грамматик BNF. Его всегда можно преобразовать в эквивалентный чистый BNF.

Однако регулярная нотация часто используется в EBNF только для того, чтобы подчеркнуть эти части синтаксиса, которые соответствуют структуре лексических элементов, и должны быть распознаны с помощью лексера, в то время как остальные с скорее представлены в прямом BNF. Но это не абсолютное правило.

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

Я бы предложил также посмотреть на ответ AHR .

Но это оставляет вопрос открытым: почему деревья?

Деревья – хорошая основа для указания синтаксиса, потому что

  • они дают простую структуру тексту

  • очень удобно связывать семантику с текстом на основе этой структуры с математически хорошо понимаемой технологией (композиционностью через гомоморфизмы), как указано выше. Это фундаментальный алгебраический инструмент для определения семантики математических формализмов.

Следовательно, это хорошее промежуточное представление, о чем свидетельствует успех абстрактных синтаксических деревьев (AST). Обратите внимание, что AST часто отличаются от дерева синтаксического анализа, потому что технология синтаксического parsingа, используемая многими специалистами (например, LL или LR), применяется только к подмножеству грамматик CF, тем самым вызывая грамматические искажения, которые впоследствии исправляются в AST. Этого можно избежать с помощью более общей технологии parsingа (основанной на динамическом программировании), которая принимает любую грамматику CF.

Заявление о том, что языки программирования являются контекстно-зависимыми (CS), а не CF, являются произвольными и спорными.

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

Многие определения языков программирования в денотационной семантике помещают объявления и проверку типов в семантике. Таким образом, заявив, что Ирак Бакстер сделал, что синтаксические анализаторы CF взломаны, чтобы получить чувствительность к контексту, требуемую синтаксисом, в лучшем случае представляет собой произвольный взгляд на ситуацию. Он может быть организован как хак в некоторых компиляторах, но это не обязательно.

Также не просто, что синтаксические анализаторы CS (в том смысле, которые используются в других ответах здесь) сложны в построении и менее эффективны. Они также неадекватны для того, чтобы наглядно продемонстрировать степень чувствительности к контексту, которая может потребоваться. И они, естественно, не создают синтаксическую структуру (например, синтаксические деревья), которая удобна для получения семантики программы, то есть для сгенерирования скомпилированного кода.

Существует ряд причин, по которым часть анализа компилятора обычно разделяется на фазы лексического анализа и анализа (синтаксического анализа).

  1. Простота дизайна – самое важное соображение. Разделение лексического и синтаксического анализа часто позволяет нам упростить хотя бы одну из этих задач. Например, парсер, который должен был иметь дело с комментариями и пробелом в качестве синтаксических единиц. Лексический анализатор уже удалил значительно сложнее, чем тот, который может принимать комментарии и пробелы. Если мы разрабатываем новый язык, разделение лексических и синтаксических проблем может привести к более продуманному общему языковому дизайну.
  2. Улучшена эффективность компилятора. Отдельный лексический анализатор позволяет применять специальные методы, которые служат только для лексической задачи, а не для синтаксического анализа. Кроме того, специализированные методы буферизации для считывания входных символов могут значительно ускорить компилятор.
  3. Улучшена переносимость компилятора. Специфические особенности, зависящие от устройства ввода, могут быть ограничены лексическим анализатором.

resource___ Компиляторы (2-е издание), написанные Альфредом В. Або Колумбийским университетом Моника С. Лам Стэнфордский университет Рави Сетти Аваей Джеффри Д. Ульман Стэнфордский университет

Давайте будем гением компьютера.