Грамматика Lisp в yacc

StackOverflow https://stackoverflow.com/questions/517113

  •  21-08-2019
  •  | 
  •  

Вопрос

Я пытаюсь создать грамматику 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");}
    ;
%%

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

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

program: slist;

slist: slist sexpr | sexpr;

Но это допускает такие проблемы, как:

( 1 1

Редактировать 2:Гибкий код таков...

%{
    #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

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

Редактировать:Ошибка была в лексере.

Это было полезно?

Решение

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

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

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

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

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

Другие советы

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

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

Вы правы в том, что вам нужно определить нетерминальный.Это было бы определено как набор 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 ++.

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

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

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

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

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

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

%start exprs

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

list:
    '(' exprs ')'
    ;

expr:
    atom
    | list
    ;

atom:
    IDENTIFIER
    | CONSTANT
    | NIL
    | '+'
    | '-'
    | '*'
    | '^'
    | '/'
    ;
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top