Question

Я пытаюсь построить REPL Smalltalk на основе LanguageKit , который использует лимонную грамматику.В настоящее время анализатор поддерживает только синтаксический анализ полных определений классов, но не операторов вне синтаксиса метода.

Например, это анализируется:

methodName [
    NSObject description.
    NSObject debugDescription.
]

Но произойдет сбой, если я попытаюсь проанализировать только операторы:

NSObject description.
NSObject debugDescription.

Следующие не будут принимать несколькооператоры (например, Transcript show: 'hello'. Transcript show: 'world'.):

file ::= statement_list(M).
{
    [p setAST:M];
}

Здесь минимальная грамматика:

%include {
#include <assert.h>
#import <Foundation/Foundation.h>
#import <LanguageKit/LanguageKit.h>
#import <LanguageKit/LKToken.h>
#import "SmalltalkParser.h"

}
%name SmalltalkParse
%token_prefix TOKEN_
%token_type {id}
%extra_argument {SmalltalkParser *p}
%left PLUS MINUS STAR SLASH EQ LT GT COMMA.
%left WORD.


file ::= method(M).
{
    [p setAST:M];
}
file ::= statement_list(M).
{
    [p setAST:M];
}
file ::= statement(M).
{
    [p setAST:M];
}
file ::= .



method(M) ::= signature(S) LSQBRACK statement_list(E) RSQBRACK.
{
    M = [LKInstanceMethod methodWithSignature:S locals:nil statements:E];
}

signature(S) ::= WORD(M).
{
    S = [LKMessageSend messageWithSelectorName:M];
}
signature(S) ::= keyword_signature(M).
{
    S = M;
}


statement_list(L) ::= statements(T).
{
    L = T;
}
statement_list(L) ::= statements(T) statement(S).
{
    [T addObject:S];
    L = T;
}

statements(L) ::= statements(T) statement(S) STOP.
{
    [T addObject:S];
    L = T;
}
statements(L) ::= .
{
    L = [NSMutableArray array];
}

statement(S) ::= expression(E).
{
    S = E;
}

%syntax_error 
{
    [NSException raise:@"ParserError" format:@"Parsing failed"];
}

message(M) ::= simple_message(S).
{
    M = S;
}

simple_message(M) ::= WORD(S).
{
    M = [LKMessageSend messageWithSelectorName:S];
}

expression(E) ::= simple_expression(S).
{
    E = S;
}

simple_expression(E) ::= WORD(T) simple_message(M).
{
    [M setTarget:T];
    E = M;
}

Полная грамматика может быть найдена здесь: smalltalk.y .Я читал другие грамматики, а также искал stackoverflow, но не вижу разницы, например, с этой грамматикой и не понимаю, почему это не работает.

rici · Answer 1 · 21 февраля 2019

В вашей грамматике есть конфликты при разборе.Они должны быть решены, если у вас есть надежда на правильную работу грамматики.

(Грамматика также имеет неопределенный нетерминал keyword_signature и неиспользуемый нетерминал message. Чтобы получитьчтобы компилировать без предупреждений, я просто удалил их. Я не думаю, что это имеет какое-либо значение для анализа ниже.)

Часть конфликта очень проста: вы не можете иметь оба

file ::= statement_list .

и

file ::= statement .

На самом деле, мне непонятно, зачем вы этого хотите?Разве statement не является примером statement_list?

Причина, по которой вы не можете иметь и то и другое, заключается в том, что у вас есть:

 statement_list ::= statements statement .

и

 statements ::= .

Взятые вместе, это означает, что начиная с statement_list, вы можетераспознать один statement.Так что ваша грамматика неоднозначна;если вход является одним оператором, он может быть непосредственно проанализирован как file или как file ⇒ statement_list ⇒ statements statement ⇒ statement с другим набором действий.

Вам может быть все равно;действительно, вы можете поверить, что последовательность действий идентична.Вы могли бы даже быть правы об этом.Но парсер не может этого знать и не поверит.Он видит два разбора как обязательно разные.Так что он сообщит о конфликте.

Короче, избавьтесь от file ::= statement ..Затем вы можете начать работать с другими конфликтами синтаксического анализа.

Более фундаментальная проблема также основана на том факте, что statements может получить пустую последовательность.

Давайте посмотримв грамматике (упрощается путем удаления всей семантики):

statement_list ::= statements .
statement_list ::= statements statement .
statements     ::= statements statement STOP .
statements     ::= .

Если statement_list не пусто, все, что соответствует, должно начинаться с пустого statements, за которым следует statement.statement, в свою очередь, должно начинаться с WORD, поэтому statement_list должно соответствовать вводу, который начинается с WORD.Но прежде чем он сможет сдвинуть WORD, чтобы продолжить анализ, ему нужно сначала вставить пустой statements.Таким образом, перед обработкой WORD он должен выполнить сокращение, используя последнее приведенное выше правило.(Если этот абзац не совсем понятен, попробуйте перечитать его, а если у вас все еще есть вопросы, задайте их. Важно понять эту часть.)

Ничего из этого не было бы проблемой, если бы нетот факт, что file также может быть method, а method также начинается с WORD.Но, в отличие от statement_list, он действительно начинается с WORD.Он не начинается с пустого statements, поэтому, если синтаксический анализатор создает пустой statements, а на самом деле ввод является method, анализ не будет выполнен.

Как это происходит, этот конкретный конфликтне появляется, если у вас file ::= statement вместо file ::= statement_list, потому что statement также не начинается с пустого statements.Это означает, что когда анализатор видит WORD в начале ввода, он еще не должен решить, собирается ли он увидеть statement или method.В обоих случаях действие разбора - сдвинуть WORD и посмотреть, что будет дальше.

Чтобы решить эту проблему, мы можем заметить, что statement_list должен содержать хотя бы один statement, и что всеstatement внутри statement_list (кроме, возможно, последнего) должны заканчиваться STOP (то есть . ).Если мы начнем с этой идеи, довольно легко создать альтернативную грамматику, которая не требует пустого списка в начале:

statement_list ::= statements .
statement_list ::= statements STOP .
statements ::= statement .
statements ::= statements STOP statement .

Это отличается от вашей грамматики в том, что она считает statement_listнепустой список разделенных точками statement s, возможно, оканчивающихся точкой, в то время как ваша грамматика рассматривает Statement_list как возможно пустой список statement s, оканчивающихся точкой, за которым следует один statement.

Поскольку я сейчас проверил грамматику, я добавляю полный тестируемый код в качестве иллюстрации того, что мы просим, когда мы запрашиваем Минимально завершенный проверяемый пример .(Я использовал C и flex, а не Objective C, но я не думаю, что это что-то меняет.)

Файл parser.y:

%include { #include <assert.h> }
file ::= method.
file ::= statement_list.
file ::= .
method ::= signature OBRAC statement_list CBRAC .
signature ::= WORD .
statement_list ::= statements STOP .
statement_list ::= statements .
statements ::= statements STOP statement .
statements ::= statement .
statement ::= expression .
expression ::= simple_expression .
simple_expression ::= WORD simple_message .
simple_message ::= WORD .
%extra_argument { int* status }
%syntax_error { *status = 1; }
%parse_failure { fprintf(stderr, "Parse failed.\n"); }
%parse_accept { fprintf(stderr, "Parse succeeded.\n"); }

Файл main.l:

%{
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "parser.h"
void* ParseAlloc(void* (*allocProc)(size_t));
void* Parse(void*, int, int, int*);
void* ParseFree(void*, void(*freeProc)(void*));

void synerr(const char* token) {
  fprintf(stderr, "Syntax error handling '%s'\n", token);
}
%}
%option noinput nounput noyywrap nodefault
%x FLUSH
%%
    void* parser = ParseAlloc(malloc);
    int status = 0;
    #define SEND(typ, val) do {                        \
       if (Parse(parser, typ, val, &status), status) { \
         synerr(yytext); BEGIN(FLUSH);                 \
       }                                               \
    } while(0)
[[:space:]]+ ;
[[:alnum:]]+ { SEND(WORD, 0); }
"["          { SEND(OBRAC, 0); }
"]"          { SEND(CBRAC, 0); }
"."          { SEND(STOP, 0); }
.            { synerr(yytext); BEGIN(FLUSH); }
<FLUSH>.+    ;
<FLUSH>\n    { status = 0; BEGIN(INITIAL); }
<<EOF>>      { if (status == 0) {
                 Parse(parser, 0, 0, &status);
                 if (status) synerr("EOF");
               }
               ParseFree(parser, free );
               return 0;
             }
%%

int main(int argc, char** argv) {
   return yylex();
}

Процедура сборки:

$ lemon parser.y
$ flex -o main.c main.l
$ gcc -std=c11 -Wall -Wno-unused-variable -o catlan -D_XOPEN_SOURCE=800 main.c parser.c

Тесты:

$ ./catlan <<< 'NSObject'
Parse failed.
Syntax error handling 'EOF'
$ ./catlan <<< 'NSObject description'
Parse succeeded.
$ ./catlan <<< 'NSObject description.'
Parse succeeded.
$ ./catlan <<< 'NSObject description. OtherObject'
Parse failed.
Syntax error handling 'EOF'
$ ./catlan <<< 'NSObject description. OtherObject otherDesc'
Parse succeeded.
$ ./catlan <<< 'NSObject description. OtherObject otherDesc.'
Parse succeeded.
$ ./catlan <<< 'NSObject description. OtherObject otherDesc extra words'
Syntax error handling 'extra'
Parse succeeded.
$ ./catlan <<< 'method [ NSObject desc]'
Parse succeeded.
$ ./catlan <<< 'method [ NSObject desc.]'
Parse succeeded.
$ ./catlan <<< 'method [ NSObject desc extra words]'
Syntax error handling 'extra'
Parse failed.
$ ./catlan <<< 'method [ NSObject desc. Second]'
Syntax error handling ']'
Parse failed.
$ ./catlan <<< 'method [ NSObject desc. Second desc]'
Parse succeeded.

Лимонный парсер REPL

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

1 Ответ

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

Лимонный парсер REPL

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

1 Ответ

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

Похожие темы