使用野牛解析數據到結構中

Question

我在夏天學到了學校的彎曲和野牛，現在我想深入一點。我無法理解Bison 3.0.2的文檔。也許你們中的一些人可以幫助我。我想解析一個表示方程的字符串，並且同時填寫一個數據結構，其中包含關於分析內容的信息。例如，說我有（ax + b）^ 2。我想讓解析器生成一個包含字符串和整數常量的結構，如下所示。

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

我已經使用flex創建了一個語言規範，並且我創建了一個使用bison的語法。所需要的只是讓這兩個人將信息放入結構中。我有一些代碼以我想要的方式工作，但我忍不住想我錯過了一些東西。在Bison文檔示例中，我使用$$或$ 1來查看它們，他們認爲它是檢查語義值？當我打印語義值時，我總是得到零。無論如何，我的代碼張貼在下面。

數學式

%{ 
#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」。我希望解析器將乘法添加到我的結構中，但解析器不按順序執行此操作。那麼有沒有更好的方法來實現我的目標？

Answer 1

您可能想知道爲什麼沒有人在四個月內回答您的問題;當它看起來像一個計算器這樣一個簡單的問題。這是因爲這不是一個簡單的問題。它是一個有很多隱藏的角落和裂縫的問題的端口。現在有相當多的野牛專家爲StackOverflow的答案做出了貢獻，他們真的知道他們的東西，並且他們都避免了這種瘟疫。如果你簡化了這個問題並一次只詢問一件事情，你可能會得到一些答案，但是你只是粘貼了一大堆代碼，然後放下了一些「哦，順便說一句，關注它！「。然而，如果有人想調試你的代碼，他們不能這樣做，因爲你錯過了一大堆關鍵的東西，比如Equation對象。 StackOverflow不是一堆免費的編碼器，你知道！閱讀一些guidance。

讓我們從簡單的事情開始吧;這$$和$1你開始的東西。你稱他們爲「語義值」。不是真的。它們是一種將值傳遞迴解析樹的機制，也是爲詞法分析器關聯令牌值以提供給解析器的機制。你總是得到一個零的原因是你永遠不會分配它在詞法分析器中的任何值首先。該值通過引用內置變量yylval進行分配。這在文檔中。讓我們把你的電話號碼作爲返回e_num標記的詞法。我可以寫這個（在math.l）：

{number}  {yylval = atoi(yytext);return(e_num);} 

這使我們現在打印數字的值：

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

它看起來好多了，如果你使用的枚舉常量的名稱，而不是那些絕對值。相當糟糕的編碼來硬編碼這些數字。

我也看到你已經創建了你的棧，並在詞法分析器上將它推到它上面。可能不是一個好計劃，但現在就放手吧。如果需要，可以將令牌與此對象值相關聯。該%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; } 

在野牛語法中，有些地方可能需要將規則右側的多個值傳回左側。這就是使用構造形式的地方，但我會留給你看看。

接下來要提到的是您描述算術表達式語法的方式。有兩個問題，主要是由於處理負片和語法形式。我們需要這裏的bit of computer science。您（主要）將表達式表示爲運算符和操作數列表，它們被視爲正則語言或喬姆斯基3型窗體。問題在於，算術表達式主要嵌套在結構中。嵌套需要上下文無關文法或喬姆斯基2型。這就是爲什麼計算器語法的所有例子都使用形式：

EXP：EXP OP EXP

，而不是您所使用的上市形式。

現在你已經使用規則層次得到一些運營商的重點在語法，但不幸的是一元減（或否定），運營商將具有比二元減法運算符優先級更高，因而應該出現在Factor規則。這就是爲什麼你會有這麼多轉變/減少衝突的原因。這只是不正確的做法。有一個原因，所有的教科書都以與你的例子不同的方式進行計算器和表達。你需要回到課本上。

這就是爲什麼人們在大學裏學習這些東西的原因。我希望這能幫助一些在未來看到類似問題的讀者。