跳至内容

编译器构造/案例研究 1

Add links
来自华夏公益教科书

案例研究 1 - 一个简单的解释器

[编辑 | 编辑源代码]

这样做是为了对一些编译技术做一个温和的介绍，并介绍一些更多的计算机科学概念。

解释器比编译器更常用，因为它们没有那么陡峭的学习曲线。后面的章节和案例研究将更深入地探讨编译器。

正在解释的语言是 Basic 的一个非常小的子集，甚至比 Tiny Basic 更小。

本案例研究的目的是使用简单的解释器来对一些编译进行温和的介绍。本章有三个代码块

  • 简单的行模式 IDE，可以与任何一个解释器一起使用。
  • Very Very Tiny Basic 的解释器。
  • Very Tiny Basic 的解释器。

VVTB 解释器只允许整型变量，并且只识别五种不同的语句（足以编写简单的程序，但不是一个严肃的编程工具）。VTB 解释器允许整型和字符串变量，并且识别十种不同的语句。这两个解释器使用不同的方法来处理表达式，以提供一些多样性。

请注意，这里提供的代码旨在尽可能清晰简单；高性能不是目标。那些不熟悉 C++ 的读者可能希望参考附录 A，该附录简要介绍了本书中使用的 C++ 结构。

非常小的 Basic - 规范

[编辑 | 编辑源代码]

行模式 IDE 非常简单：如果你输入的行以数字开头，那么该行就是要添加到你的程序源代码中的语句，否则它是对系统的命令（例如 RUN 或 LIST）。行模式“编辑器”也非常简单

  • 只输入一个行号而不输入任何代码会导致任何具有该行号的现有行被删除。
  • 如果你使用的行号与以前输入的一些行的行号相同，那么早期的行将被丢弃。
  • 程序行按行号顺序排序，因此你可以轻松地插入缺少的行（如果需要），前提是你最初使用的是有间隙的行号（每 10 个是一个常见的值）。

对于词法分析 

  Digit        ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
  LineNumber   ::= Digit [ Digit ]* ;
  WholeNumber  ::= Digit [ Digit ]* ;
 
  Letter       ::= 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' |
                   'J' | 'K' | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R' |
                   'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z' ;
  
  LiteralString::= '"' [any character except double-quote]+ '"'  ;
  Comparison   ::= '=' | '<>' | '<' | '<=' | '>' | '>=' ;
  Separator    ::= ',' | ';' ;
  AddSub       ::= '+' | '-' ;
  MulDiv       ::= '*' | '/' ;

对于 IDE 处理 

  Line         ::= CommandLine | ProgramLine ;
  CommandLine  ::= 'RUN' | 'LIST' | 'NEW' | 'QUIT' ;
  ProgramLine  ::= LineNumber | Statement ;

对于 VVTB 语法分析 

  Statement    ::= 'LET' Variable '=' Expression |
                   'IF' Test 'THEN' LineNumber |
                   'PRINT' [ [ PrintItem ] Separator ]* |
                   'REM' [any character]+ |
                   'GOTO' LineNumber ; 
  Variable     ::= Letter ;
  PrintItem    ::= Expression | LiteralString ;
  Test         ::= Expression Comparison Expression ;
  Expression   ::= [AddSub] Secondary [ AddSub Secondary ]* ;
  Secondary    ::= Primary [ MulDiv Primary ]* ;
  Primary      ::= '(' Expression ')' | Variable | WholeNumber ;

对于 VTB 语法分析 

  Statement    ::= 'LET' Variable '=' Expression |
                   'IF' Test 'THEN' LineNumber |
                   'PRINT' [ [ PrintItem ] Separator ]* |
                   'REM' [any character]+ |
                   'GOTO' LineNumber |
                   'GOSUB' LineNumber
                   'RETURN' |
                   'STOP' |
                   'FOR' Variable '=' Expression 'TO' Expression ['STEP' Expression] |
                   'NEXT' Variable ; 
  Variable     ::= Letter | Letter '$' ;
  PrintItem    ::= Expression ;
  Test         ::= Expression Comparison Expression ;
  Expression   ::= [AddSub] Secondary [ AddSub Secondary ]* ;
  Secondary    ::= Primary [ MulDiv Primary ]* ;
  Primary      ::= '(' Expression ')' | Variable | WholeNumber | LiteralString ;

IDE 命令

行号

行号必须是非零的。

NEW

开始一个新程序，删除任何现有的源代码。

QUIT

终止 IDE。

LIST

列出当前的源代码。

RUN

执行当前的源代码。

示例程序

[编辑 | 编辑源代码]

Very Very Tiny Basic 中的程序非常简单。Very Tiny Basic 中的程序仍然很简单，但它们可以做更复杂的事情。这两种语言都不允许任何用户输入。

示例 VVTB 程序 

REM This is a sample VVTB program.

10 LET a = 10

20 PRINT "The value of a is ", a

30 LET b = 20

40 IF b < 40 THEN 10

示例 VTB 程序 

REM This is a sample VTB program.

10 FOR a$ = 1 TO 50 STEP 5

20 FOR b = 1 TO a$

30 GOSUB 200

50 NEXT b

60 NEXT a$

70 FOR b = 1 TO 100

80 GOSUB 200

90 IF b > 25 THEN 500

100 NEXT b

REM A sub-routine will return to where it is called from.

200 PRINT "The value of a$ is ", a

210 PRINT "The value of b is ", b

220 RETURN

500 PRINT "Exiting the program."

510 GOTO 1000

1000 STOP

行模式 IDE - 实现

[编辑 | 编辑源代码]

下面的代码可能看起来很短，但它确实是一个完整的行模式 IDE。它之所以如此短，是因为使用了 C++ 的 <map>，这正是存储源代码、按行号排序行等所需的东西。

//------ standard C++ headers --------------------------

#include <cctype>
#include <iostream>
#include <map>
#include <cstdlib>
#include <string>

using namespace std;

//------ functions: IDE --------------------------------

// Main loop of line-mode IDE.
void LineModeIDE(void);
 
// Obey command.
void ObeyCommand(const string Command,      // Command to obey.
                 map<int,string> & Source,  // Program source code.
                 bool & Continue);          // Set false to terminate. 
 
// Obtain next non-blank line.
string NextNonBlankLine(void);

// Split line into number and text.
void SplitLine(const string & Line,  // Line to be split.
               int & Number,         // 0 or number at start of line.
               string & Text);       /* Remainder of line, if any,
                                        converted to upper case. */

//------ functions: interpreter ------------------------

// Interpret program.
void Interpret(map<int,string> & Source);  // Program source code.

//------ main program ---------------------------------- 

int main(int argc, char* argv[])
{
    LineModeIDE();
    return 0;
}

//------ function definitions --------------------------

// Main loop of line-mode IDE.
void LineModeIDE(void)
{
    map<int,string> Source;   // Program source code.
    int CurNumb;              // 0 or current line number.
    string CurText;           // Rest of text on line.
    bool Continuing = true;   // true=keep going.
     
    while ( Continuing ) {
        SplitLine(NextNonBlankLine(),CurNumb,CurText);
        if ( CurNumb == 0 ) {
            ObeyCommand(CurText,Source,Continuing);
        } else if ( CurText == "" ) {
            Source.erase(CurNumb);
        } else {
            Source[CurNumb] = CurText;
        }
    }
} 


// Obey command.
void ObeyCommand(const string & Command,    // Command to obey.
                 map<int,string> & Source,  // Program source code.
                 bool & Continue)           // Set false to terminate.
 {
     if ( Command == "QUIT" ) {
         Continue = false;
     } else if ( Command == "NEW" ) {
         Source.clear();
     } else if ( Command == "RUN" ) {
         Interpret(Source);
     } else if ( Command == "LIST" ) {
         map<int,string>:: iterator Ndx;
         for ( Ndx = Source.begin();
               Ndx != Source.end();
               ++Ndx 
             ) {
             cout << Ndx->first << ' ' << Ndx->second << endl;
         }
     } else {
         cout << "*** unrecognised command: "
              << Command << endl;
     }
}  

// Obtain next non-blank line.
string NextNonBlankLine(void)
{
    string Line;
    int First,Last;
    do {
        cout << ':';
        getline(cin,Line);
        First = 0;
        Last  = Line.length() - 1;
        while ( First<=Last && Line[First]==' ' ) {
            ++First;
        }
        if ( First > Last ) {
            Line = "";
        }
    } while ( Line == "" );
    return Line;
}

// Split line into number and text.
void SplitLine(const string & Line, // Non-blank line to be split.
               int & Number,        // 0 or number at start of line.
               string & Text)       /* Remainder of line, if any,
                                       converted to upper case. */
{
    int Ndx = 0;
    int Value = 0;
    int Last = Line.length() - 1;
    string Result;
    while ( Line[Ndx] == ' ' ) {    // Skip leading spaces.
        ++Ndx;
    }
    while ( isdigit(Line[Ndx]) ) {  // Extract any number.
        Value = Value*10 + (int(Line[Ndx]) - int('0'));
        ++Ndx;
    }
    Number = Value;
    while ( Line[Ndx] == ' ' ) {    // Skip more spaces.
        ++Ndx;
    }
    while ( Line[Last] == ' ' ) {   // Ignore trailing spaces.
        --Last;
    }
    while( Ndx <= Last ) {          // Copy non-blank portion,
        Result += toupper(Line[Ndx]);  // as upper case.
        ++Ndx;
    }
    Text = Result;
}

// Interpret program.
void Interpret(map<int,string> & Source) // Program source code.
{
    cout << "Sorry, interpreter not yet available." << endl;
}

非常小的 Basic - 一个解释器

[编辑 | 编辑源代码]
Clipboard

待办事项
完成

取自 "https://wikibooks.cn/w/index.php?title=Compiler_Construction/Case_Study_1&oldid=3357628"
华夏公益教科书