本篇內容

• 範例 - 簡易計算機3

介紹

我們在昨天介紹了Recursion，並比較了左遞迴與右遞迴的差別。
今天，我們將實際將recusion運用在parser中，來看看是否能夠達成我們預想的規則匹配。

範例 - 簡易計算機3

說明

請實作出一個簡易的計算機，能夠對多個正整數做運算(加與減其中之一)，並回傳結果。

輸入範例

4 + 7 + 6 - 5 =

輸出範例

Result: 12

程式實作

• Lex實作
  • 由上述測資範例可知，跟之前相比多了等號，因此在lex檔案中需要新增等號的token
• Yacc實作
  • 使用OR語法處理加法與減法規則
  • 使用recursion語法處理連續的加減法運算
  • 新增func規則，在讀取到等號時，印出運算結果

完整程式碼

Lex

%{
#include "main.h"
#include "yacc.tab.h"
%}

posint      ([0-9]+)
blank_chars ([ \f\r\t\v]+)
expressions ([-+])

%%

{posint}        { yylval = atoi(yytext); return NUMBER; }
{expressions}   { return yytext[0]; }
{blank_chars}   { ; }
"="             { return yytext[0]; }
\n              { ; }

%%

int yywrap(void) {
    return 1;
}

Yacc

%{
#include "main.h"

void yyerror(const char *s);
extern int yylex();
extern int yyparse();

%}

%token NUMBER

%%

func:
      expr '='              { printf("Result: %d\n", $1); }
    ;

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

%%

void yyerror(const char *s) {
    cerr << s << endl;
}

Main

• main.h

#ifndef MAIN_H
#define MAIN_H

#include <iostream>
#include <stdio.h>

using namespace std;

#define YYSTYPE int
#endif

• main.cpp

#include "main.h"
#include "yacc.tab.h"

extern int yyparse(void);
extern FILE* yyin;

int main()
{
    const char* sFile = "file.txt";
    FILE* fp = fopen(sFile, "r");
    if (fp == NULL) {
        printf("cannot open %s\n", sFile);
        return -1;
    }
    
    yyin = fp;
    yyparse();

    fclose(fp);

    return 0;
}

執行結果

輸入內容

4 + 7 + 6 - 5 =

輸出結果

Result: 12

結語

今天我們將recusion的語法實際應用在簡易計算機的例子中。
然而，在編譯時卻出現了警告訊息。

yacc.y: conflicts: 4 shift/reduce

我們明天要來好好研究一下，到底發生了甚麼事？

參考資料

• Levine, John R., Tony Mason and Doug Brown [1992]. Lex & Yacc. O’Reilly & Associates, Inc. Sebastopol, California.
• Tom Niemann. Lex & Yacc