編譯器構造/案例研究 1
< 編譯器構造
這樣做是為了對一些編譯技術做一個溫和的介紹，並介紹一些更多的計算機科學概念。
直譯器比編譯器更常用，因為它們沒有那麼陡峭的學習曲線。後面的章節和案例研究將更深入地探討編譯器。
正在解釋的語言是 Basic 的一個非常小的子集，甚至比 Tiny Basic 更小。
本案例研究的目的是使用簡單的直譯器來對一些編譯進行溫和的介紹。本章有三個程式碼塊
- 簡單的行模式 IDE，可以與任何一個直譯器一起使用。
- Very Very Tiny Basic 的直譯器。
- Very Tiny Basic 的直譯器。
VVTB 直譯器只允許整型變數，並且只識別五種不同的語句（足以編寫簡單的程式，但不是一個嚴肅的程式設計工具）。VTB 直譯器允許整型和字串變數，並且識別十種不同的語句。這兩個直譯器使用不同的方法來處理表達式，以提供一些多樣性。
請注意，這裡提供的程式碼旨在儘可能清晰簡單；高效能不是目標。那些不熟悉 C++ 的讀者可能希望參考附錄 A，該附錄簡要介紹了本書中使用的 C++ 結構。
行模式 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。它之所以如此短，是因為使用了 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;
}
