1

我正在尝试基于LanguageKit构建一个 Smalltalk REPL ，它使用柠檬语法。目前解析器只支持解析完整的类定义，不支持解析方法语法之外的语句。

例如，这被解析：

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，但没有看到例如这个语法的区别，也不明白为什么这不起作用。

4

1 回答 1

2

您的语法存在解析冲突。如果您希望使语法正常工作，则必须解决这些问题。

（该语法还有一个未定义的非终结符keyword_signature, 和一个未使用的非终结符message。为了让它在没有警告的情况下编译，我只是删除了它们。我认为这对下面的分析没有任何影响。）

冲突的一部分很简单：你不能同时拥有

file ::= statement_list .

和

file ::= statement .

事实上，我不清楚你为什么要这样做？不是statement一个例子statement_list吗？

你不能两者兼得的原因是你有：

 statement_list ::= statements statement .

和

 statements ::= .

综上所述，这意味着从 开始statement_list，您可以识别单个statement。所以你的语法是模棱两可的；如果输入是单个语句，则可以直接将其解析为 afile或者可以将其解析为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也可以是 a method，并且method也以 a 开头，那么这一切都不是问题WORD。但是，与 不同statement_list的是，它实际上是从 开始的WORD。它不以 empty 开头statements，因此如果解析器创建了一个 emptystatements并且输入实际上是 a method，那么解析将失败。

file ::= statement碰巧的是，如果您有而不是，则不会发生这种特定的冲突file ::= statement_list，因为statement也不是以空开头statements。这意味着当解析器WORD在输入的开头看到 a 时，它还不必决定是要看到 astatement还是 a method。在这两种情况下，解析操作都是转移WORD并看看接下来会发生什么。

为了解决这个问题，我们可以观察到statement_list必须至少包含一个statement，并且 a 中的所有statements statement_list（可能最后一个除外）都必须以 a 结束STOP（即.）。如果我们从这个想法开始，很容易产生一种替代语法，它在开始时不需要一个空列表：

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

这与您的语法不同，因为它认为 astatement_list是点分隔的非空列表，statement可选地以点结尾，而您的语法认为 statement_list 可能是点终止statement的 s 的空列表，后跟一个statement.

由于我现在已经测试了语法，因此我添加了完整的可测试代码，以说明我们在请求Minimal Complete Verifiable Example时所要求的内容。（我使用 C 和 flex 而不是 Objective C，但我认为这没有任何区别。）

文件解析器.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.
于 2019-02-20T23:11:16.573 回答