Существует ли грамматика LL(k) для PCF?

Мы работаем над синтаксическим анализом сверху вниз в классе разработки компилятора. Примерами являются все java-подобные языки. Я решил попробовать простой функциональный язык, чтобы сделать его интересным, поэтому я выбрал PCF (см., например, здесь ). Однако я не могу понять это в грамматике LL (1). Я думаю, что проблема заключается в применении функции (т.е. сопоставлении двух выражений). Я не получаю четких ответов о том, как определить, является ли это просто моим недостатком навыков или это язык, для которого нет грамматики LL (1) или LL (k), если уж на то пошло. Может кто-нибудь пояснить, мне просто нужно быть умнее или такой грамматики просто не существует?

По сути, моя версия PCF похожа на скетч ниже (прописные буквы не являются терминалами, комментарий начинается с "//"). Я говорю «что-то вроде», потому что я не привязан именно к этому, и я написал много вариантов - просто хочу разумный вариант PCF.

Обратите внимание, что я пробовал левофакторинг и учет старшинства с промежуточными нетерминалами.

Exp -> Const     // integer and boolean literals, normal ops e.g. +
    |  if Exp then Exp else Exp
    |  lambda identifier dot Exp    //lambda (function) abstraction
    |  Exp Exp                      // function application
    |  fix Exp                      // fixpoint operator (recursion)

parsing functional-programming lambda-calculus
person joeA    schedule 29.02.2016    source источник
comment
Это стандартное устранение левой рекурсии, см., например, здесь . Основная идея состоит в том, что грамматика A -> A α | β эквивалентна A -> β A'; A' -> ε | α A'. Вы должны обобщить случай с большим количеством βs.   -  person Bakuriu    schedule 29.02.2016
comment
@Bakuriu Я пытался исключить левую рекурсию, но, возможно, я сделал это только для прямой левой рекурсии. Мне придется еще раз взглянуть на вашу ссылку относительно косвенной части. Тем не менее, эта ссылка говорит что-то об испорченной ассоциативности, с которой я тоже боролся.   -  person joeA    schedule 29.02.2016

Ответы (1)


arrow_upward
1
arrow_downward

Проблема в том, что ваша грамматика является леворекурсивной, что плохо работает с парсерами сверху вниз, как описано в LL(k).

В частности, попытка проанализировать Exp приводит к попытке сначала проанализировать первую часть приложения-функции Exp Exp..., что для нисходящего анализатора создает бесконечный цикл.

Вероятным решением в вашем случае будет реализация приложения функции произвольной длины в праворекурсивном стиле:

AppExp -> Exp | Exp AppExp

Exp -> Const | (AppExp) | ...

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

AppExp  -> Exp | AppExp Exp

будет таким же леворекурсивным, как и исходный.

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

 application expression:    f a b c d
   |
   |  LL(1) parse
   v
 right-associative   --->   left-associative
       @             list              @
      / \          reversal           / \
     f   @                           @   d
        / \                         / \
       a   @                       @   c
          / \                     / \
         b   @                   @   b
            / \                 / \
           c   .               .   a
               |               |
               d               f

Библиотеки синтаксических анализаторов Combinator, такие как Parsec, обычно имеют удобные предварительно упакованные функции, которые сделают это за вас.

С точки зрения теории языка это демонстрирует различие между языком, принимаемым грамматикой, и анализом, производимым синтаксическим анализатором на основе этой грамматики....

person comingstorm    schedule 29.02.2016
comment
Извините, если я был неясен. Я знаю, что пример грамматики является непосредственно леворекурсивным, и я попытался удалить левую рекурсию (и обработать приоритет и ассоциативность всех операторов) с некоторыми грамматиками, которые оказались намного больше. Однако я думаю, что они все же не LL(1) (косвенно леворекурсивны в приложении?). Я пытался понять, не лаю ли я просто не на то дерево. Я думаю, возможно, это то, о чем вы говорите - отказаться от LL(1) и сделать это по-другому - но мне придется переварить ваш ответ, когда у меня будет время. - person joeA; 29.02.2016
comment
Мой ответ рекомендует способ придерживаться LL (1) и работать с тем, что может дать вам нисходящий парсер. Я подозреваю, что вы лаяли не по тому дереву, но урок, который следует здесь усвоить, заключается в том, что в подобных случаях устранение левой рекурсии исказит ваш порядок синтаксического анализа, независимо от того, как вы пытаетесь его нарезать. - person comingstorm; 29.02.2016
comment
Другими словами: вы можете создать грамматику LL(1), которая будет распознавать ваш язык; мой ответ показывает вам пример. Однако ваш комментарий предполагает, что вы также хотите, чтобы ваша грамматика анализировала синтаксис вашего приложения левоассоциативным способом, который не будет работать для LL(1) или почти для любого типа верхнего уровня. вниз синтаксический анализатор меньше, чем полностью общий. - person comingstorm; 01.03.2016
comment
Итак, метод, который я рекомендую (особенно, поскольку ваш класс работает над главой синтаксического анализа сверху вниз), состоит в том, чтобы использовать грамматику LL (1), которая распознает ваш язык (даже если она не анализирует его в нужном вам порядке) , и исправьте порядок синтаксического анализа потом. - person comingstorm; 01.03.2016
comment
Еще раз спасибо за разработку. Я посмотрю на это еще. Возможно, одно место, где я заблудился, это то, что инструктор, кажется, объединяет две идеи, которые вы разделяете. Думаю, инструктор сказал бы, что грамматика LL(1) для PCF будет неверной, независимо от того, какой язык она принимает, если она приведет к дереву синтаксического анализа / AST, которое не отражал правильную/желаемую ассоциативность без приспособлений вне грамматики. Мы не сделали ничего, кроме дополнительного шага после разбора сверху вниз для внесения дополнительных грамматических исправлений. - person joeA; 01.03.2016
comment
Добавлено несколько изображений ascii, чтобы продемонстрировать ассоциативное обращение. - person comingstorm; 01.03.2016