2

tl;dr：#define你如何在不做预处理步骤的情况下用 jison模拟 C 的等价物？

我正在研究一种相对简单的语法，该语法具有将标识符分配给代码块的功能，然后为了简洁起见，以后可以重复使用。例子：

# Valid grammar with various elements of different types
foo x.3 y.4 z.5

# Assign an id to a chunk of code. Everything after -> is assigned to id
fill_1-> bar a.1 b.2 c.3

# Use chunk of code later
# Should be equivalent to parsing: "baz d.4 bar a.1 b.2 c.3 e.5"
baz d.4 ["fill_1"] e.5

到目前为止，我的解析器设置已正确识别代码的分配行并将“->”右侧的部分存储在可用于其他解析器操作的字典中。与下面提供的定义操作相关的代码：

// Lexer
HSPC                      [ \t]
ID                        [a-zA-Z_][a-zA-Z0-9_]*
%%
{ID}{HSPC}*"->"       {
                        this.begin("FINISHLINE"); 
                        yytext = yytext.replace("->", "").trim();
                        return "DEFINE";
                      }

('"'{ID}'"')          { 
                        yytext = yytext.slice(1,-1);
                        return "QUOTED_ID"; 
                      }

<FINISHLINE>.*        {
                        this.begin("INITIAL");
                        yytext = yytext.trim();
                        return "REST_OF_LINE";
                      }

%%

// Parser
statement
  : "[" QUOTED_ID "]"
    { $$ = (defines[$2] ? defines[$2] : ""); }
  | DEFINE  REST_OF_LINE
    { 
      defines[$1] = $2;
    }
  ;

%% 
var defines = {};

如何让 jison 真正标记和解析保存的代码片段？我需要采用 AST 方法吗？有没有办法将代码注入解析器？这应该发生在词法分析阶段还是解析阶段？希望听到可以通过简短示例片段采取的多种策略。

谢谢！

4

3 回答 3

2

如果通过“采用 AST 方法”，您的意思是“为原始未替换程序和替代程序构建 AST，并将它们拼接在一起”，那么您将遇到困难。无法保证您的替换字符串与语法中的任何有效非终结符匹配，因此为它构建树并不容易。替换之前的主程序也极不可能被您的完整语法解析。[您可以通过构建子字符串解析器和使用树片段粘合进行魔法来克服这些困难，但是会做很多工作[我们正在为 C 预处理器分析器做类似的事情]，我怀疑 ANTLR 对您有多大帮助]。

通常的方法是让词法分析器保留一堆部分读取的输入流，底部流是主程序，嵌套流对应于部分读取的宏调用（如果一个宏可以调用另一个宏，则需要多个. 当然你的语言允许“fill2 -> x.1 [fill1] y.3”？这意味着词法分析器必须：

  • 识别宏定义，因此它可以访问名称和宏内容之间的映射
  • 识别宏调用（不干扰词法分析或解析状态；通常这意味着宏调用必须由词法分析器中的临时机器识别）
  • 在流堆栈上“推送”被调用宏的输入流
  • 到达流末尾时“弹出”流堆栈

您可能有一天会决定在宏上需要参数。您通常也可以将它们实现为流。

您可以想象对令牌进行词法分析并存储令牌流而不是文本作为宏主体；那么宏调用检测和正文插入可能发生在词法分析器之后和解析器之前。由于它们两者之间可能存在一个接口，因此在两者之间放置代码来管理它似乎是一种实用的方法。如果您的语言允许相同的字符流在程序的不同位置以不同的方式解释，则可能会出现复杂情况；在这种情况下，宏捕获如何知道如何对宏内容进行分类？

我对 ANTLR3 的了解不够（甚至很多），无法详细告诉您如何完成此操作。

于 2013-12-30T07:38:41.337 回答
1

实现像 C 预处理器这样的预处理器的常用方法是让它处理词法分析器和解析器之间的令牌流。因此，词法分析器识别标记，将输入的字符流转换为标记流，然后预处理器对该标记流进行操作，将其转换为新的标记流，最后解析器解析该标记流。

现在，如果您使用的是 yacc/lex（或 bison/flex），这有点棘手，因为它们被设计为通过解析器调用直接yylex通信，中间没有任何内容。使用 flex，您可以使用YY_DECL宏来更改yylex它定义的函数的声明，并插入您自己的yylex函数：

%{
#define YY_DECL static int token()
%}
%%
 ... lex rules
%%

int yylex() {
    int tok = token();
    if (tok == IDENTIFIER) {
        Macro *mac = find_macro(yylval.str);
        if (mac) {
            yypush_buffer_state(dummy_buffer);
            yy_scan_string(mac->definition);
            return yylex(); } }
    return tok;
}

使用 lex，您可以在适当的位置使用#define yylex token/#undef yylex来获得相同的效果。

于 2014-01-02T16:31:13.500 回答
0

因此，在进一步阅读之后，这是一种不需要预处理的潜在方法。

我现在在我的解析器中为不同类型的节点生成一个抽象语法树。我的 AST 由各种类组成，一些代表基本单位，另一些代表元单位。我的“宏”用它们自己的 AST 元素表示，它包含对已解析 AST 元素集合的引用。因此，我没有进行代码替换然后多次解析的“代码替换”，而是一次解析定义的块并存储对创建的 AST 元素的引用。例如：

# fundamental units
class TabElement
# subclasses of TabElement
class NoteElement
class SlideElement
class MuteElement

# meta element: holds a collection of TabElements's
class NoteGroupElement
# meta element: holds a collection of TabElements's and otherstatements, has an ID
#               the collection is accessible via a global dict to other elements
class PredefElement
# meta element: represents a usage of a PredefElement
class PredefInvokeElement

这样做的缩写词法分析器和解析器规则如下所示（省略了很多无关的东西，希望你能明白）：

/* LEXER */
<INITIAL>[\s]             /* ignore whitespace */
{ID}{HSPC}*"->"       {
                        this.begin("DEFINE"); 
                        yytext = yytext.replace("->", "").trim();
                        return "DEFINE";
                      }
/* using a pre-def */
('"'{ID}'"')|("'"{ID}"'") { 
                        yytext = yytext.slice(1,-1);
                        return "QUOTED_ID"; 
                      }

/* When defining a code chunk.  Newlines delimit the end of the definition */
<DEFINE>{HSPC}            /* ignore horizontal whitespace */
<DEFINE>({NL}|<<EOF>>)    { this.begin("INITIAL"); return "NL"; }

/* PARSER */
statement
  : statement_group
    { $$ = $1; }
  | DEFINE statements NL
    { 
      defines[$1] = new ast.PredefinedElement($1, $2, @1);
      $$ = defines[$1]
    }
  | predefine_invoke
    { $$ = $1; }
  | chord
    { $1 = $1; }
  | bar_token
    { $$ = $1; }
  | REPEAT_MEASURE
    { $$ = new ast.RepeatMeasureElement(@1); }
  | REST
    { $$ = new ast.RestElement(@1); }
  | DURATION
    { $$ = new ast.DurationElement($1, @1); }
  | note_token
    { $$ = $1; }
  ;

predefine_invoke
  : "[" QUOTED_ID "]"
    %{ 
      if (defines[$2]) { $$ = new ast.PredefinedInvokeElement(defines[$2], @2); } 
      else { $$ = undefined; }
    %}
  | "[" QUOTED_ID "]" "*" INTEGER
    %{ 
      if (defines[$2]) { $$ = new ast.PredefinedInvokeElement(defines[$2], @2, { repeat: parseInt($5) }); } 
      else { $$ = undefined; }
    %}
  ;
于 2014-01-01T23:45:03.067 回答