Построение дерева синтаксического анализа Lisp / Scheme с помощью flex / bison

Я пытался разобрать простой код, похожий на Lisp / схему

E.g. (func a (b c d) )

и построить из него дерево, я мог бы выполнить синтаксический анализ на C без использования bison (т. е. используя только flex для возврата токенов и построения дерева с рекурсией). Но с грамматикой bison я не уверен, куда добавить код для построения списка (т. Е. какое правило связать с накоплением терминальных символов и где связать построенный список с родительским узлом).

Моя грамматика похожа на приведенную здесь: Грамматика Лиспа в yacc грамматика правильная и может распознать код.


parsing flex-lexer lisp s-expression bison
person vyom    schedule 30.06.2010    source источник
comment
Я изменил теги с flex на gnu-flex, несмотря на встречный совет: meta.stackexchange.com/questions/26460/tag-for-two-flexes/ просто потому, что многим посетителям сайта сложно увидеть значок Adobe на теге. Надеюсь, это скоро будет рассмотрено. Желаем удачи получить ответ на свой вопрос.   -  person mechanical_meat    schedule 30.06.2010
comment
Для синтаксического анализа простых S-выражений вам вряд ли понадобятся flex или bison. Вы должны уметь закодировать это как простой рекурсивный анализатор спуска с вручную скрученным лексером для атомов, круглых скобок и пропуска пробелов в чем-то вроде сотни строк C или меньше. Исходные интерпретаторы LISP, безусловно, делали это с помощью очень небольшого фрагмента кода.   -  person Ira Baxter    schedule 30.06.2010
comment
Ира: Правда в том, что в парсере нет необходимости, но скрученный вручную лексер работает только с обычными игрушечными подмножествами, с которыми обычно сталкиваются люди. У некоторых Lisps / Schemes есть токены, которые могут быть очень волосатыми. Для вашего развлечения вот пример действительной числовой константы в Racket: #e#x+e#s+e@-e#l-e.   -  person Eli Barzilay    schedule 30.06.2010
comment
@Ira: да, я мог бы написать синтаксический анализатор на чистом C (я уже упоминал об этом в своем вопросе). Но я хотел знать, как создаются настоящие парсеры из flex / bison.   -  person vyom    schedule 05.07.2010
comment
@Eli Barzley: Может быть, вам нужен лексер для полноценной современной шепелявости, такой как Racket. ОП сказал: «Просто».   -  person Ira Baxter    schedule 05.07.2010
comment
@vyom Да, вы могли бы продолжить, используя bison, и в качестве чистого опыта это было бы хорошо. Если возникает вопрос, как мне использовать Bison для этого? правильный ответ: знайте, когда вам следует использовать инструмент, а когда нет. Когда разбор прост, вам не нужно и не следует использовать большой молоток. Как часть идеи чистого образования, я думаю, вы сочтете полезным написать версию на чистом C для построения ваших деревьев, а также версию bison, чтобы вы понимали, как использование чего-то вроде bison искажает способ построения ваших деревьев. И я сделаю это первым.   -  person Ira Baxter    schedule 05.07.2010
comment
Ира: Не существует простой современной не игрушечной шепелявости.   -  person Eli Barzilay    schedule 05.07.2010

Ответы (1)


arrow_upward
3
arrow_downward

Вы пробовали разместить код для добавления элемента в текущий список в каждом атоме и код для управления деревом списков при обработке скобок? Это кажется самым простым способом, если вы не столкнетесь с другими проблемами:

listend: members ')'        { cur = cur->parent; }
       | ')'                { cur = cur->parent; }
       ;

list: '(' listend           { cur = newList(cur);}
    ;

atom: ID                    { appendAtom(cur, "ID"); }
    | NUM                   { appendAtom(cur, "NUM");}
    | STR                   { appendAtom(cur, "STR");}
    ;

Это предполагает, что вы сохраняете родительскую точку в каждой структуре списка.

person Andrew    schedule 08.07.2010
comment
Привет, Амосс, я не пробовал использовать родительский указатель, попробую этот подход. Спасибо. - person vyom; 08.07.2010
comment
vjom: Это сработало? В таком случае, пожалуйста, отдайте должное Амоссу, приняв ответ :) - person Baggers; 03.05.2013