使用野牛将数据解析为结构

问题描述 投票：1回答：1

我在暑假期间在学校里了解了屈曲和野牛，现在我想更深入地学习。我在理解Bison 3.0.2的文档时遇到了麻烦。也许有些人可以帮助我。我想解析一个表示方程式的字符串，同时填写一个数据结构，其中包含有关已解析内容的信息。例如，假设我有（ax + b）^ 2。我希望解析器生成一个结构，该结构包含一个字符串和一个如下所示的整数常量。

(  BEGINGROUP
a  VARIABLE
x  VARIABLE
+  ADDITION
b  VARIABLE
)  ENDGROUP

我已经使用flex创建了语言规范，并且已经使用bison创建了语法。需要做的就是让两者将信息放入结构中。我有一些代码可以按照我想要的方式工作，但是我不禁觉得自己缺少了一些东西。在Bison文档示例中，我看到它们使用$$或$ 1，它们表示要检查语义值？当我打印语义值时，我总是得到零。无论如何，我的代码发布在下面。

math.l

%{
 #include "equation.h"

Equation* equ;
void setEquation(Equation* equation) {
    equ = equation;
}
%}

/* Definitions */
space     [ \t]
digit     [0-9]
letter    [a-zA-Z]
number    ({digit}+|{digit}+"."{digit}+|"."{digit}+|{digit}+".")
variable  {letter}

/* actions */
%%
{space}      ;
{number}     equ->addElement(yytext, Equation::number); return(1);
{variable}   equ->addElement(yytext, Equation::variable); return(2);  
"+"          equ->addElement(yytext, Equation::addition); return(10); /* Basic operators */
"-"          return(11);
"*"          return(12);
"/"          return(13);
"^"          return(14);
"log"        return(15); 
"sin"        return(20); /* Trigonometric Functions */
"cos"        return(21);
"tan"        return(22);
"csc"        return(23);              
"sec"        return(24);
"cot"        return(25);
"arcsin"     return(26);
"arccos"     return(27);
"arctan"     return(28); 
"("          equ->addElement(yytext, Equation::begGroup); return(30); /* Grouping Operators */
")"          equ->addElement(yytext, Equation::endGroup); return(31);
"["          return(32);
"]"          return(33);
","          return(34);
.            fprintf(stderr, "Error on character %s\n", yytext);

math.y

/*
* Implement grammer for equations
*/
%{
#include "lex.yy.c"
#include "equation.h"
#include <iostream>

int yylex(void);
int yyerror(const char *msg);

void output(const char* where) {
    std::cout << where << ": " << yytext << std::endl;
}
%}

%token e_num       1
%token e_var       2
%token e_plus     10
%token e_minus    11
%token e_mult     12
%token e_div      13
%token e_pow      14
%token e_log      15 
%token e_sin      20
%token e_cos      21
%token e_tan      22
%token e_csc      23              
%token e_sec      24
%token e_cot      25
%token e_asin     26
%token e_acos     27
%token e_atan     28 
%token lparen     30
%token rparen     31
%token slparen    32
%token srparen    33
%token comma      34
%start Expression
%%

Expression : Term  MoreTerms 
           | e_minus Term MoreTerms
           ;
MoreTerms  : /* add a term */
             e_plus Term MoreTerms
           | /* subtract a term */
             e_minus Term MoreTerms
           | /* add a negetive term */
             e_plus e_minus Term MoreTerms /* Add a negetive term */
           | /* minus a negetive term */
             e_minus e_minus Term MoreTerms /* Subtract a negetive term */
           | /* no extra terms */
           ;
Term       : Factor MoreFactors {equ->addElement("*", Equation::multiplication)};
           ;
MoreFactors: e_mult Factor MoreFactors
           | e_div  Factor MoreFactors
           | Factor MoreFactors
           |
           ;
Factor     : e_num { std::cout << $1 << std::endl; } //returns zero no matter where I put this
           | e_var
           | Group 
           | Function 
           ;
BeginGroup : lparen | slparen; 
EndGroup   : rparen | srparen;
Group      : BeginGroup Expression EndGroup 
              ;

Function   : TrigFuncs
           | PowerFunc
           ;
TrigFuncs  : e_sin lparen Expression rparen
           | e_cos lparen Expression rparen
           | e_tan lparen Expression rparen
           | e_csc lparen Expression rparen
           | e_sec lparen Expression rparen
           | e_cot lparen Expression rparen
           | e_asin lparen Expression rparen
           | e_acos lparen Expression rparen
           | e_atan lparen Expression rparen
           ;
PowerFunc  : e_num e_pow Factor
           | e_var e_pow Factor
           | Group e_pow Factor
           | TrigFuncs e_pow Factor
           ;

我认为我在做什么很清楚。如您所见，扫描程序将yytext及其代码存储到等式类中，但是有时解析器必须向等式类中添加信息，这会使事情变得忙碌。一方面，尝试在语句之前或之中添加代码会导致大量的移位/减少冲突。其次，将代码放在语句末尾的作用是使内容混乱地记录下来。查看条款规则。如果我键入“ ax”，则意味着“ a”乘以“ x”或“ a * x”。我希望解析器将乘法添加到我的结构中，但是解析器会无序地执行此操作。那么有没有更好的方法可以实现我的目标？

c++ bison
1个回答
2
投票

您可能想知道为什么四个月内没有人回答您的问题；当看起来像计算器这样简单的问题时。这是因为这不是一个容易回答的问题。它是一个问题的Portmanteau，为那些粗心的人提供了许多隐藏的角落和缝隙。现在，有很多野牛专家对Stack Overflow的答案做出了贡献，他们真的知道他们的知识，而且所有人都像瘟疫一样避免了这种情况。如果您简化了问题并一次只问了一件事，那么您可能会得到一些答案，但是您只是粘贴了全部代码，然后添加了一些“哦，顺便说一句，再说吧！”。但是，如果有人想调试您的代码，则不会这样做，因为您错过了整个关键任务，例如Equation对象。你不知道StackOverflow不是一堆免费的编码器！阅读一些guidance。

让我们从简单的事情开始；您开始使用的$$和$1内容。您称它们为“语义值”。并不是的。它们是一种将值通过解析树传递回去的机制，也使词法分析器将令牌值关联给解析器。您总是得到零的原因是，您首先从不会在词法分析器中为其赋予任何值。该值通过引用内置变量yylval来分配。在文档中。让我们以您的数字lexeme为例，它返回一个e_num令牌。我可以这样写（在math.l中）：{number} {yylval = atoi(yytext);return(e_num);} 

这使我们现在可以打印数字的值：

Factor : e_num { std::cout << $1 << std::endl; } 

如果使用枚举常量的名称而不是那些绝对值，则看起来会更好。这样的编码很难将这些数字固定在一起。

我还看到您已经创建了堆栈并将其放入lexer中。可能不是一个好计划，但现在就放弃吧。如果需要，可以将令牌与这样的对象值相关联。 %union结构（在野牛中）用于：

%union { Equation* TokenValue; } 

现在，您必须开始输入语法的结尾和非结尾：

%token <TokenValue> e_enum; 

但是现在，如果您愿意，我们可以使用这些结构来获得价值：

{number} {equ->addElement(yytext, Equation::number); yylval.TokenValue = equ; return(e_num); } 

和野牛：

Factor : e_num { std::cout << $1->ElementText << std::endl; } 

在野牛语法中，您可能希望将多个值从规则的右侧传递回左侧。这是将使用$$ = $2形式的构造物的地方，但我将让您继续阅读。

接下来要提到的是您描述算术表达式语法的方式。存在两个问题，主要是由于处理否定词和语法形式。

这里需要bit of computer science。 （主要）将表达式表示为运算符和操作数的列表，这被视为

Regular Language

或Chomsky Type 3形式。问题是算术表达式主要嵌套在结构中。嵌套需要上下文无关语法或Chomsky类型2。这就是所有计算器语法示例都使用以下形式的原因：exp：exp OP exp

而不是您使用的列表。

现在您已经使用规则层次结构来获得语法中运算符的某些优先级，但是不幸的是，一元减（或负）运算符的优先级高于二进制减法运算符，因此应出现在Factor中规则。这些就是为什么您会发生许多移位/减少冲突的原因。这不是正确的方法。所有教科书都以与示例不同的方式来做计算器和表达式是有原因的。您需要返回教科书。

这就是为什么人们在大学学习这些东西的原因。希望对以后正在研究类似问题的读者有所帮助。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.