柠檬解析器 REPL
Lemon Parser REPL
我正在尝试构建一个基于 LanguageKit 的 Smalltalk REPL，它使用了柠檬语法。目前解析器只支持解析完整的 class 定义，但不支持方法语法之外的语句。
例如，这被解析为：
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. I have been reading other grammas and also searching Whosebug, but don't see a difference for example with this 不明白为什么这不起作用。
您的语法存在解析冲突。如果您希望使语法正常工作，则必须解决这些问题。
（该语法还有一个未定义的非终结符 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。 （如果这一段不是很清楚，请尝试重新阅读，如果您还有疑问，请提问。理解这部分很重要。）
None 如果不是因为 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_list中的所有statement（除了可能最后一个）必须以 STOP 结尾（即 .）。如果我们从这个想法开始，就很容易产生一个不需要开头空列表的替代语法：
statement_list ::= statements .
statement_list ::= statements STOP .
statements ::= statement .
statements ::= statements STOP statement .
这与您的语法不同，因为它认为 statement_list 是点分隔的 statement 的非空列表，可选地以点结尾，而您的语法认为 statement_list 可能是一个以点结尾的 statement 后跟一个 statement 的空列表。
因为我现在已经测试了语法，所以我添加了完整的可测试代码作为我们在请求 Minimal Complete Verifiable Example 时请求的内容的说明。 （我使用 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.
我正在尝试构建一个基于 LanguageKit 的 Smalltalk REPL，它使用了柠檬语法。目前解析器只支持解析完整的 class 定义，但不支持方法语法之外的语句。
例如，这被解析为：
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. I have been reading other grammas and also searching Whosebug, but don't see a difference for example with this
您的语法存在解析冲突。如果您希望使语法正常工作，则必须解决这些问题。
（该语法还有一个未定义的非终结符 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。 （如果这一段不是很清楚，请尝试重新阅读，如果您还有疑问，请提问。理解这部分很重要。）
None 如果不是因为 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_list中的所有statement（除了可能最后一个）必须以 STOP 结尾（即 .）。如果我们从这个想法开始，就很容易产生一个不需要开头空列表的替代语法：
statement_list ::= statements .
statement_list ::= statements STOP .
statements ::= statement .
statements ::= statements STOP statement .
这与您的语法不同，因为它认为 statement_list 是点分隔的 statement 的非空列表，可选地以点结尾，而您的语法认为 statement_list 可能是一个以点结尾的 statement 后跟一个 statement 的空列表。
因为我现在已经测试了语法，所以我添加了完整的可测试代码作为我们在请求 Minimal Complete Verifiable Example 时请求的内容的说明。 （我使用 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.