0

我目前开始学习YACC。我只想知道如何在 YACC 中编写属性语法。请举个例子。我们可以使用 union 吗？

4

4 回答 4

2

是的，您可以将属性与解析树中的节点相关联。每个节点都有一个属性，即“美元说明符”。这是一个示例，其中属性用于表达式的值：

expression : expression '+' expression { $$ = $1 + $3; }
           | expression '-' expression { $$ = $1 - $3; }
           | NUMBER { $$ = $1; }
           ;

默认情况下，这个单一属性是一个整数，但您可以使用%union指令更改类型。不同类型的节点可以具有不同类型的属性。（这就是为什么它被称为%union而不是%type之类的东西。）如果您需要多个属性，则可以使用 C 结构或结构指针作为类型。

于 2013-10-14T08:26:55.657 回答
2

是的，您需要使用一些 C++ 功能：对于 AST 树存储，使用基于Sym 抽象类的“符号”类集。虚拟继承使您能够使用Sym*指针以及dynamic_cast<Num*>(o)STL 容器和对象操作。使用attr{}map 作为语法属性。

完整的 (c) 词法程序框架 (c) 源代码树参见https://github.com/ponyatov/uc/tree/master/ast

struct Sym {        // universal algebraic symbolic type, struct applies public
    string tag;         // class/type marker, required for token elements
    string val;         // value, string is universal can represent _any_ data

    Sym(string T,string V);     // <T:V> pair constructor
    Sym(string V);              // token constructor

    vector<Sym*> nest;          // \ nest[]ed elements for AST tree
    void push(Sym*o);           // / push new nested element

    map<string,Sym*> attr;      // \ named dynamic attributes,
    double num ;                // / or extra attributes you need

    virtual string head();      // return "<T:V>" pair repr
    string pad(int);            // pad output of tree elements
    string dump(int depth=0);   // return tree dump
};

struct Num: Sym { Num(string);      // number tokens
    double val; string head(); };
struct Str: Sym { Str(string);      // 'string' tokens
    string head(); };

struct Vector: Sym { Vector(); };   // [vector]
struct Op: Sym { Op(string); };     // operator

typedef Sym*(*FN)(Sym*);                        // \ primitive function
struct Fn: Sym { Fn(string V, FN F); FN fn; };  // /

                                // == lexer interface ==
extern int yylex();             // get next token
extern int yylineno;            // line number
extern char* yytext;            // parsed lexeme (ASCIIZ string)
#define TOC(C,X) { yylval.o = new C(yytext); return X; } // gen.token macro
                                // == syntax parser interface ==
extern int yyparse();           // grammar parser
extern void yyerror(string);    // error callback function
#include "ypp.tab.hpp"          // shared lex/yacc token definitions

注意 lpp.lpp 中使用的词法分析器接口宏，用于表单中的令牌构造

[0-9]+(\.[0-9]*)?([eE](\+\-)?[0-9]+)?   TOC(Num,NUM)    /* number */

对于答案，请参阅上面的语法必须描述为

%defines %union { Sym*o; }
%token <o> NUMBER ADD SUB
%type <o> expression

expression : expression ADD expression {
    // build AST node
    $$=$2; $$->push($1); $$->push($3);
    // synth .num attribute from nested nodes
    $$->num = $1->num + $3->num ;
    }

expression : expression SUB expression {
    // build AST node
    $$=$2; $$->push($1); $$->push($3);
    // synth .num from nested nodes
    $$->num  = $1->num - $3->num ;
    }

expression : NUMBER { $$=$1; } /* terminal should be used directly */

或者如果你想要真正的符号方式：这个 yacc 语法将在（在 C++ 中非常神秘，但在 Python+PLY 语法中看起来很清晰）中执行动态可合成属性attr{}

%%
REPL : | REPL ex { cout << $2->dump() << endl; } ;

ex : SYM                { $$=$1; /* terminal as is */ } ;
ex : NUM                { $$=$1; /* terminal as is */
    // synth
    $$->attr["num"] = new Num(dynamic_cast<Num*>($1)->val);
    } ;

ex : SYM LP ex RP       { $$=new Op("@");               // apply operator
                          $$->push(new Fn($1->val));    // new function
                          $$->push($3);                 // parameters
    // synth
    if ($1->val=="sin")
        $$->attr["num"] = new Num(std::sin(\
            dynamic_cast<Num*>($3->attr["num"])->val));
    } ;

ex : LP ex RP           { $$=$2; /* as is */ } ; // must be after SYM(ex)

ex : ex DIV ex          { $$=$2; $$->push($1); $$->push($3);
   $$->attr["num"] = new Num(\
    dynamic_cast<Num*>($1->attr["num"])->val \
    / \
    dynamic_cast<Num*>($3->attr["num"])->val \
    );
   } ;

给树

<op:=> #0x5b1180
    <sym:A> #0x5b1118
    <op:+> #0x5b1348
        <op:-> #0x5b11e8
            1 #0x5b1250
                num =
                    1 #0x5b12a8
        <op:*> #0x4a07d8
            <op:+> #0x5b13b0
                2.3 #0x5b1418
                    num =
                        2.3 #0x5b1470
            <op:^> #0x4a1090
                4e-005 #0x4a1010
                    num =
                        4e-005 #0x4a1050
                <op:/> #0x5bb730
                    num =
                        -0.0399165 #0x5bb850
                    <op:@> #0x5bb648
                        num =
                            -0.279415 #0x5bb6d0
                        <fn:sin> #0x5bb680
                        6 #0x5bb570
                            num =
                                6 #0x5bb5b0
                    7 #0x5bb768
                        num =
                            7 #0x5bb7a8

(*) 回答：请在问题中注意属性语法关键字。

于 2017-02-08T05:56:41.097 回答
1

网络上有很多 yacc 语法的例子。一个简单的 google 搜索yacc 示例会显示很多链接。这里还有很多有用的链接

于 2013-10-09T18:06:25.437 回答
1

我你更喜欢最简单的方法，是的，使用这个语法：：@ https://github.com/ponyatov/uc/blob/master/ast/union.yacc

此变体仍然构建带注释的 AST 树，但将属性硬编码到类中。如果您需要额外的属性，请使用虚拟继承，并手动（通过生产规则）跟踪属性树的有效性。

%defines %union {
    struct AST {
        string name;
        double value;
        virtual string dump(int depth=0);
        vector<AST*> nest; void push(Sym*);
    } *node;
}

/* tokens name/value must be filled in lexer */

%token <node> SYM NUM EQ ADD SUB MUL DIV POW LP RP
%type <node> ex  
                    // precedence down higher
%right EQ
%left ADD SUB
%left MUL DIV
%right PFX

%%
REPL : | REPL ex    { cout << $2->dump() << endl } ;

ex : SYM            { $$=$1; } ; // token as is
ex : NUM            { $$=$1; } ; // token as is

ex : ADD ex %prec PFX {
    $$=$1; $$->push($2);                // unary operator AST subtree
    $$->value = + $2->value;            // + A
    };
ex : SUB ex %prec PFX {
    $$=$1; $$->push($2);                // unary operator AST subtree
    $$->value = - $2->value;            // - A
    };

ex : ex ADD ex      {
    $$=$2; $$->push($1); $$->push($3);  // build AST subtree
    $$->value = $1->value + $2->value;  // synth attr without cryptic code
    } ;

ex : ex MUL ex      {
    $$=$2; $$->push($1); $$->push($3);  // build AST subtree
    $$->value = $1->value * $2->value;  // synth attr without cryptic code
    } ;

真的，yacc-ng应该支持 %struct 选项来直接构建 AST 树，但yacc不能这样做，你应该嵌套struct*在%union.

于 2017-02-08T07:19:49.960 回答