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

308

Действительно ли лексеры и парсеры в теории отличаются друг от друга

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

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

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

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

Нэвин
источник
2
да. Я пытаюсь разобрать autohotkey. Я смог быстро создать подсветку синтаксиса, используя фрагменты. Но antlr занимает намного больше времени ... Я не видел много перекрестного опыления между этими двумя инструментами.
Навин
67
Только модно ненавидеть регулярные выражения, когда ими злоупотребляют. Многие люди пытаются использовать регулярные выражения, когда требуется анализ без контекста. Они всегда терпят неудачу. И они обвиняют технологию регулярных выражений. Это все равно, что жаловаться на то, что ваш молоток - вялая пила. Правда, но вы не получите много сочувствия.
Ира Бакстер
2
К счастью, я начинаю набирать скорость с помощью antlr. Большая часть лексизма не зависит от контекста, а иногда даже зависит от контекста.
Навин
1
Один фундаментальный аспект проблемы лексера и парсера заключается в том, что лексеры основаны на конечных автоматах (FSA) или, точнее, конечных преобразователях (FST). Большинство формализмов анализа (не только Context-Free) закрыты на пересечении с FSA или применением FST. Следовательно, использование более простого регулярного выражения на основе формализма для лексера не увеличивает сложность синтаксических структур более сложных синтаксических формализмов. Это абсолютно важный вопрос модульности при определении структуры и семантики языков, который, к счастью, игнорируется ответами с высоким голосом.
Бабу
Следует отметить, что лексеры и парсеры не должны быть разными, например, LLLPG и более ранние версии ANTLR используют одну и ту же систему парсинга LL (k) для лексеров и парсеров. Основное отличие состоит в том, что регулярных выражений обычно достаточно для лексеров, но не для синтаксических анализаторов.
Qwertie

Ответы:

475

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

  1. Они читают символы некоторого алфавита из своего ввода.

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

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

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

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

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

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

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

  • Уровень 3: Обычные грамматики

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

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

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

SasQ
источник
70
О да? Так что же это за слова или жетоны? Это просто предложения на обычном языке, состоящие из букв алфавита. И что это за "конструкции" или "деревья" в парсере? Это также предложения , но на другом языке более высокого уровня, для которых конкретные токены являются алфавитными символами. Разница не в том, что вы сказали, а в сложности используемого языка . Сразитесь с -1 с помощью любого справочника по теории парсинга.
SasQ
3
@SasQ Было бы справедливо сказать, что и Lexers, и парсеры принимают в качестве входных данных некоторую грамматику и серию токенов?
Параг
4
Совершенно так. Они оба берут серию символов из алфавита, который они узнают. Для лексера этот алфавит состоит только из простых символов. Для парсера алфавит состоит из терминальных символов, какими бы они ни были определены. Они также могут быть символами, если вы не используете лексер и используете однозначные идентификаторы, однозначные числа и т. Д. (Весьма полезно на первых этапах разработки). Но они обычно являются токенами (лексическими классами), потому что токены - хорошая абстракция: вы можете изменить фактические лексемы (строки), которые они обозначают, и анализатор не увидит изменения.
SasQ
6
Например, вы можете использовать символ терминала STMT_ENDв вашем синтаксисе (для синтаксического анализатора) для обозначения конца инструкций. Теперь вы можете иметь связанный с ним токен, сгенерированный лексером. Но вы можете изменить фактическую лексему, которую он обозначает. Например. Вы можете определить STMT_ENDкак ;иметь C / C ++ - как исходный код. Или вы можете определить его так, endчтобы он был похож на стиль Паскаля. Или вы можете определить его как '\n'конец инструкции с конца строки, как в Python. Но синтаксис инструкции (и синтаксический анализатор) остается неизменным :-) Необходимо изменить только лексер.
SasQ
24
Часы в Википедии и Google не помогли, но вы объяснили грамматику Хомского за 3 минуты. Спасибо.
enrey
107

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

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

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

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

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

Ира Бакстер
источник
40
Хорошее объяснение, Ира. Добавим к вашей аналогии: в то время как лексеры говорят о правильных словах, парсеры - о правильных предложениях. «Точечный запуск» и «Точный просмотр» действительны в том, что касается лексера. Требуется синтаксический анализатор, чтобы определить, что структура фразы неправильна (в грамматике английского языка).
Алан
Я думаю, что парсер для лексера, как дерево ходок для парсера. Я не уверен, что теория такова: antlr.org/wiki/display/~admin/ANTLR+v4+lexers, но я начинаю понимать различия в соглашениях между ними ...
Навин
4
Теория очень отличается. Большинство технологий синтаксического анализа пытаются до некоторой степени обрабатывать языки без контекста (некоторые делают только часть, например, LALR, некоторые делают все это, например, GLR). Большинство технологий lexer только пытаются делать регулярные выражения.
Ира Бакстер
3
Теория другая, потому что она была предложена многими разными людьми и использует различную терминологию и алгоритмы. Но если вы внимательно посмотрите на них, вы можете заметить сходство. Например, проблема левой рекурсии очень похожа на проблему недетерминированности в NFA, а удаление левой рекурсии аналогично удалению недетерминизма и преобразованию NFA в DFA. Токены - это предложения для токенизатора (вывод), но алфавитные символы для парсера (ввод). Я не отрицаю различия (уровни Хомского), но сходство очень помогает в дизайне.
SasQ
1
Мой соратник был в теории категорий. Он показал, как понятие категориальной теории пучков охватывает все виды сопоставления с образцом, и смог получить разбор LR из абстрактной категориальной спецификации. Так что на самом деле, если вы будете достаточно абстрактны, вы сможете найти такие общие черты. Суть теории категорий в том, что вы часто можете абстрагироваться «до конца»; Я уверен, что вы могли бы создать синтаксический анализатор теории категорий, который бы стирал различия. Но любое практическое использование этого должно быть осуществлено до конкретной проблемной области, и тогда различия проявятся как реальные.
Ира Бакстер
32

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

EBNF действительно не добавляет много силы грамматике. Это просто удобное / сокращенное обозначение / «синтаксический сахар» по сравнению со стандартными грамматическими правилами Хомского в нормальной форме (CNF). Например, альтернатива EBNF:

S --> A | B

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

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

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

S --> X?

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

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

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

Повторение нуля или более от EBNF:

S --> A*

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

S --> S A    // `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.

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

S --> A S    // `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.

И когда дело доходит до +одного или нескольких повторений от ЕБНФ:

S --> A+

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

S --> A A*

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

S --> A S   // `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неопределенное время, что всегда будет добавлять другие as и bs с обеих сторон. Лексеры (точнее: конечные автоматы, используемые лексерами) не могут сосчитать до произвольного числа (они конечны, помните?), Поэтому они не знают, сколько было as, чтобы сопоставить их равномерно с таким количеством bs. Такие грамматики называются контекстно-свободными грамматиками (по крайней мере), и для них требуется синтаксический анализатор.

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

A R B --> A S B

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

SasQ
источник
1
Вы утверждаете, что EBNF - это «просто удобная / сокращенная запись /« синтаксический сахар »по сравнению со стандартными правилами грамматики Хомского в нормальной форме (CNF)». Но CNF вряд ли имеет какое-либо отношение к данной теме. EBNF может быть легко преобразован в стандартный BNF. Период. Это синтаксический сахар для стандартных БНФ.
Бабу
11

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

Лексеры и парсеры не сильно отличаются, как предполагает принятый ответ. Оба основаны на простых языковых формализмах: обычные языки для лексеров и, почти всегда, контекстно-свободные (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 (в том смысле, в каком они здесь используются в других ответах) сложны и менее эффективны. Они также неадекватны для того, чтобы явно выразить вид контекстной чувствительности, который может потребоваться. И они, естественно, не создают синтаксическую структуру (такую ​​как деревья разбора), которая удобна для получения семантики программы, то есть для генерации скомпилированного кода.

Babou
источник
Да, деревья разбора и AST различны, но не очень полезны. Смотрите мое обсуждение этого: stackoverflow.com/a/1916687/120163
Ира Бакстер
@IraBaxter Я не согласен с вами, но сейчас у меня нет времени, чтобы составить четкий ответ на ваш пост. По сути, вы придерживаетесь прагматической точки зрения (и, я думаю, также защищаете свою собственную систему). Это даже проще, потому что вы используете общие синтаксические анализаторы CF (однако GLR, возможно, не самый эффективный), а не детерминированные, как в некоторых системах. Я рассматриваю AST как эталонное представление, которое поддается формально определенному лечению, корректно корректным преобразованиям, математическим доказательствам, разбору нескольких конкретных представлений и т. Д.
babou
«Прагматичный» взгляд - это причина, по которой я утверждаю, что они не очень отличаются полезным способом. И я просто не верю, что использование (ad hoc AST) дает вам «достоверно правильные преобразования»; Ваш специальный AST не имеет очевидного отношения к фактической грамматике обрабатываемого языка (и здесь, да, моя система оправданна тем, что наш "AST" является доказуемо изоморфным эквивалентом BNF). Специальные AST не дают вам никакой дополнительной возможности разбирать «множественные конкретные представления». Вы возражаете против GLR (не самый эффективный), кажется довольно бессмысленным. И при этом они не являются недетерминированными.
Ира Бакстер,
Так что на самом деле я не понимаю какую-то часть вашего возражения против моего комментария. Вам придется написать этот «чистый ответ».
Ира Бакстер
@IraBaxter Комментарии слишком ограничены для правильного ответа (предложение?). «Ad hoc» не является подходящим определителем для AST, которого я защищаю, что должно быть (иногда является) эталонным синтаксисом. Это исторически верно, если смотреть как на историю концепции AST в информатике, так и на историю формальных систем как терминов (деревьев) в отсортированной алгебре вместе с интерпретацией. AST - это справочная форма, а не производная. Смотрите также современные проверочные системы и автоматическое создание программ. Вы можете быть предвзятым из-за того, что вам нужно работать с конкретным синтаксисом, разработанным другими.
Бабу
7

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

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

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

AHR
источник