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

Question

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

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

Спасибо за вашу помощь, Чарли.

PS: Я собираюсь написатьсинтаксический анализатор с использованием библиотеки Parsec Haskell.

РЕДАКТИРОВАТЬ: Кроме того, в соответствии с SK-логикой, Parsec может обрабатывать бесконечную перспективу (LL (k)?) - но я думаю, вопрос все еще стоит для этого типа грамматики.

Answer 1

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

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

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

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

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

ANSI C грамматика

Python грамматика

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

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

Answer 2

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

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

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

Answer 3

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

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

Есть два основных правила для создания грамматики LL (1)

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