Написание правильных грамматик LL (1)?

Question

В настоящее время я пытаюсь написать (очень) небольшой интерпретатор/компилятор для языка программирования. Я установил синтаксис для языка, и теперь мне нужно записать грамматику для языка. Я намерен использовать парсер LL (1), потому что, после небольшого исследования, кажется, что он проще всего использовать.

Я новичок в этом домене, но из того, что я собрал, настоятельно рекомендуется формализовать синтаксис с использованием BNF или EBNF. Однако кажется, что не все грамматики подходят для реализации с использованием анализатора LL (1). Поэтому мне было интересно, какой был правильный (или рекомендуемый) подход к написанию грамматик в форме LL (1).

Благодарим за помощь, Charlie.

PS: Я намерен написать парсер, используя библиотеку Parsec от Haskell.

EDIT: Кроме того, согласно SK-логике, Parsec может обрабатывать бесконечный lookahead (LL (k)?) - но я думаю, что этот вопрос по-прежнему относится к такому типу грамматики.

Answer 1

Я не эксперт в этом, так как я сделал только небольшой проект с парсером LR (0). Общий подход, который я бы рекомендовал:

1. Получите работу с арифметикой. Таким образом, создайте правила и определения для +, -, /, * и т. Д. И убедитесь, что синтаксический анализатор создает дерево абстрактных синтаксисов. Проверьте и оцените дерево на разных входах, чтобы убедиться в правильности арифметики. Сделайте вещи шаг за шагом. Если вы столкнулись с каким-либо конфликтом, сначала разрешите его, прежде чем двигаться дальше.

2. Получите простые конструкции, работающие как if-then-else или case выражения, работающие.

3. Идет дальше в большей степени зависит от языка, на котором вы пишете грамматику.

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

ANSI C grammar

Python grammar

и, конечно, некоторые небольшие примеры в Википедии о LL грамматик Wikipedia LL Parser, что вы, вероятно, уже проверили.

Я надеюсь, что вы найдете некоторые из этих вещей полезных

Answer 2

Существуют алгоритмы как для определения, является ли грамматика LL (к). Генераторы Parser реализуют их. Существуют также эвристики для преобразования грамматики в LL (k), если это возможно.

Но вам не нужно, чтобы ограничить простой язык для LL (1), так как большинство современных генераторов парсеров (JavaCC, ANTLR, Pyparsing и другие) могут обращаться с любым к в LL (к).

Что еще более важно, это очень вероятно, что синтаксис вы считаете лучше для вашего языка требует k между 2 и 4, так как несколько конструкций общего программирования делать.

Answer 3

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

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

Там две основные правила большого пальца, чтобы сделать грамматики LL (1)

1. Если из нескольких вариантов может появиться в данной точке, и они могут начать с тем же самым, добавьте ключевое слово в передней рассказывая вы, который выбрал .
2. Если у вас есть дополнительная или повторяющаяся часть, сделайте уверенным, что за ней следует конечный токен, который не может появиться в качестве первого жетона дополнительной/повторной части.
3. Избегайте дополнительных деталей в начале производства, где это возможно. Это делает первые два шага намного проще.