Когда достаточно лексизма, когда вам нужен 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, используя nullable продукцию, то есть ту, которая может быть заменена пустой строкой (обозначается здесь просто пустой продукцией; другие используют epsilon или лямбда или перечеркнутый круг):
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.
Зная, что он генерирует только пустую строку (в конечном итоге), за которой следует ноль или более A с, эту же строку (, но не тот же язык! ) можно выразить, используя right- рекурсия
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.
И когда дело доходит до + за одно или несколько повторений от EBNF:
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 на неопределенный срок, что всегда добавит еще a s и b s с обеих сторон. Лексеры (точнее: конечные автоматы, используемые лексерами) не могут сосчитать до произвольного числа (они конечны, помните?), Поэтому они не знают, сколько было a с, чтобы сопоставить их равномерно с таким количеством b s. Грамматики, подобные этой, называются контекстно-свободными грамматиками (как минимум), и для них требуется синтаксический анализатор.
Общеизвестно, что контекстно-зависимые грамматики разбираются, поэтому они широко используются для описания синтаксиса языков программирования. Но это еще не все. Иногда требуется более общая грамматика - когда у вас есть много вещей, чтобы сосчитать одновременно, независимо. Например, когда вы хотите описать язык, в котором можно использовать круглые скобки и квадратные скобки с чередованием, но они должны быть правильно спарены друг с другом (фигурные скобки с круглыми скобками). Этот вид грамматики называется контекстно-зависимым . Вы можете распознать его по тому, что у него более одного символа слева (перед стрелкой). Например:
A R B --> A S B
Вы можете рассматривать эти дополнительные символы слева как «контекст» для применения правила. Могут быть некоторые предварительные условия, постусловия и т. Д. Например, вышеприведенное правило будет заменять R на S, но только когда оно находится между A и B, оставляя эти A и B самими неизменными. , Этот вид синтаксиса действительно трудно разобрать, потому что ему нужна полноценная машина Тьюринга. Это совсем другая история, поэтому на этом я закончу.