Лисп грамматика в yacc

Question

Я пытаюсь построить грамматику Lisp. Легко, правда? Видимо нет.

Я представляю эти входные данные и получаю ошибки ...

( 1 1)
23 23 23 
ui ui

Это грамматика ...

%%
sexpr: atom                 {printf("matched sexpr\n");}
    | list
    ;
list: '(' members ')'       {printf("matched list\n");}
    | '('')'                {printf("matched empty list\n");}
    ;
members: sexpr              {printf("members 1\n");}
    | sexpr members         {printf("members 2\n");}
    ;
atom: ID                    {printf("ID\n");}
    | NUM                   {printf("NUM\n");}
    | STR                   {printf("STR\n");}
    ;
%%

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

edit - это был мой подход "верхнего терминала":

program: slist;

slist: slist sexpr | sexpr;

Но это разрешает такие проблемы, как:

( 1 1 

Edit2: код FLEX ...

%{
    #include <stdio.h>
    #include "a.yacc.tab.h"
    int linenumber;
    extern int yylval;
%}
%%
\n                         { linenumber++; }
[0-9]+                     { yylval = atoi(yytext); return NUM; }
\"[^\"\n]*\"               { return STR; }
[a-zA-Z][a-zA-Z0-9]*       { return ID; }
.
%%

Пример слишком подходящего ...

(1 1 1)
NUM
matched sexpr
NUM
matched sexpr
NUM
matched sexpr
(1 1
NUM
matched sexpr
NUM
matched sexpr

В чем здесь ошибка?

edit: ошибка была в лексере.

Answer 1

Ошибка действительно в лексере. Ваши скобки заканчиваются последним "." в лексере и не отображаются в скобках в парсере.

Добавить правила вроде

\)     { return RPAREN; }
\(     { return LPAREN; }

для лексера и измените все вхождения '(', ')' на LPAREN и RPAREN соответственно в парсере. (также вам нужно #define LPAREN и RPAREN, где вы определяете свой список токенов)

Примечание: я не уверен в синтаксисе, возможно, обратная косая черта неверна.

Answer 2

Грамматика Lisp не может быть представлена ​​как контекстно-свободная грамматика, а yacc не может проанализировать весь код lisp. Это из-за функций lisp, таких как чтение-оценка и программируемый ридер. Таким образом, для того, чтобы просто прочитать произвольный код lisp, вам нужно запустить полный lisp. Это не какая-то неясная, неиспользуемая функция, но она фактически используется. Например, CL-INTERPOL, CL-SQL.

Если цель состоит в том, чтобы проанализировать подмножество lisp, то текст программы представляет собой последовательность sexprs.

Answer 3

Вы правы в том, что вам нужно определить нетерминал. Это будет определяться как набор sexpr. Я не уверен в синтаксисе YACC для этого. Я неравнодушен к ANTLR для генераторов синтаксического анализатора и синтаксис будет:

program: sexpr*

с указанием 0 или более sexpr.

Обновление с синтаксисом YACC:

program :  /* empty */
        | program sexpr
        ;

Не в YACC, но может быть полезен в любом случае, вот полная грамматика в ANTLR v3, которая работает для описанных вами случаев (исключая строки в лексере, потому что это не важно для этого примера, также использует вывод консоли C #, потому что это то, что я проверил это с):

program: (sexpr)*;

sexpr: list
    |  atom            {Console.WriteLine("matched sexpr");}
    ;

list:     
   '('')'              {Console.WriteLine("matched empty list");}
   | '(' members ')'   {Console.WriteLine("matched list");}

    ;

members: (sexpr)+      {Console.WriteLine("members 1");};

atom: Id               {Console.WriteLine("ID");}
    | Num              {Console.WriteLine("NUM");}
    ;


Num: ( '0' .. '9')+;
Id: ('a' .. 'z' | 'A' .. 'Z')+;
Whitespace : ( ' ' | '\r' '\n' | '\n' | '\t' ) {Skip();};

Это не будет работать точно так же, как в YACC, потому что YACC генерирует и анализатор LALR, в то время как ANTLR является модифицированным рекурсивным спуском. Если вы хотите пойти по этому пути, для ANTLR есть выходная цель C / C ++.

Answer 4

Вам обязательно нужен парсер yacc / bison? Считыватель "читает подмножество синтаксиса lisp" не так сложно реализовать в C (начните с функции read_sexpr, отправьте в read_list, когда увидите '(', который, в свою очередь, строит список содержащихся sexprs до тех пор, пока '' ) ', в противном случае вызовите read_atom, который собирает атом и возвращает его, когда он больше не может читать символы, составляющие атом).

Однако, если вы хотите иметь возможность читать произвольный Common Lisp, вам нужно (в худшем случае) реализовать Common Lisp, поскольку CL может изменять время выполнения считывателя (и даже переключаться между различными таблицами чтения). время выполнения под управлением программы; очень удобно, когда вы хотите загрузить код, написанный на другом языке или на диалекте lisp).

Answer 5

Я только что попробовал, моя "грамматика yacc lisp" работает нормально:

%start exprs

exprs:
    | exprs expr
    /// if you prefer right recursion :
    /// | expr exprs
    ;

list:
    '(' exprs ')'
    ;

expr:
    atom
    | list
    ;

atom:
    IDENTIFIER
    | CONSTANT
    | NIL
    | '+'
    | '-'
    | '*'
    | '^'
    | '/'
    ;

Answer 6

Вы можете попробовать эту грамматику здесь .

Answer 7

Прошло много времени с тех пор, как я работал с YACC, но вам действительно нужен терминал без верхнего уровня. Не могли бы вы поподробнее сказать «попробовал» и «похоже, это не сработало»? Или, если на то пошло, что за ошибки?

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