我目前开始学习YACC。我只想知道如何在 YACC 中编写属性语法。请举个例子。我们可以使用 union 吗？
问问题
1586 次
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
我你更喜欢最简单的方法，是的，使用这个语法：：@ 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 回答