代码之家 › 专栏 › 技术社区 › catlan

柠檬语法分析器

lemon grammar parsing

1

catlan · 技术社区 · 7 年前

我正在尝试建立一个基于 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,但没有看到与此示例的区别 gramma 我不明白为什么这不起作用。

0 回复 | 直到 7 年前

1

2

rici 7 年前

您的语法有解析冲突。如果你希望语法正确,就必须解决这些问题。

keyword_signature ,以及一个未使用的非终端 message . 为了让它在没有警告的情况下编译,我只是删除了它们。我认为这对下面的分析没有任何影响。)

file ::= statement_list .

和

file ::= statement .

statement 一个例子 statement_list ?

您不能同时拥有这两种功能的原因是:

 statement_list ::= statements statement .

 statements ::= .

总而言之,这意味着从 报表清单 ,你可以认出一个 . 所以你的语法是模棱两可的;如果输入是单个语句,则可以将其直接解析为 file 或者可以将其解析为 文件 报表清单 statements statement 陈述 ,使用一组不同的操作。

总之,摆脱 file ::= statement . . 然后可以开始处理其他解析冲突。

更根本的问题也基于以下事实: statements 可以派生空序列。

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

如果 报表清单 不是空的,无论它匹配什么,都必须以空开头接着是 . 陈述 WORD 所以 报表清单 必须匹配以开头的输入 单词 . 但在它改变现状之前为了继续解析,它需要首先插入空的 声明 . 因此,它需要使用上面引用的最后一条规则进行缩减,然后才能处理 单词 . (如果这一段不完全清楚,请尝试重读,如果你还有问题,请提问。理解这一部分很重要。)

文件 也可能是一个 method 和 方法 . 但是,不像 报表清单 ,这真的是从 单词 . 它不是以空字符开头的 声明 声明 而输入实际上是一个 方法 ,则解析将失败。

碰巧的是,如果您有 file ::= statement 而不是 file ::= statement_list 陈述 不是以空的开始任何一个这意味着当解析器看到在输入开始时,它还不必决定是否要看到 陈述 或者 方法 单词

为了解决这个问题,我们可以观察到 报表清单 必须至少包含一个 陈述 陈述 它在一个房间里 报表清单 STOP . ).如果我们从这个想法开始,很容易产生一个替代语法,它不需要在开始时列出一个空的列表:

statement_list ::= statements .
statement_list ::= statements STOP .
statements ::= statement .
statements ::= statements STOP 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.