// --------------- test99.c0 ---------------------
for (i=1; i<=9; i++)
{
 for (j=1; j<=9; j++)
 {
 println(i, "*", j, "=", i*j);
 }
}

// ------------------ Interpreter.cs ---------------------------
// 執行共需兩個檔案
//
// 程式檔 : Interpreter.cs
// 測試檔 : sum.c0
//
// 編譯方式 : csc Interpreter.cs
// 執行方式 : Interpreter sum.c0
// -------------------------------------------------------------
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Text.RegularExpressions;
namespace Compiler
{
 public class Program
 {
 // 測試主程式。
 static void Main(string[] args)
 {
 C3Parser parser = new C3Parser(IO.fileToText(args[0]));
 Tree parseTree = parser.parse();
 Interpreter interpreter = new Interpreter(parseTree);
 interpreter.run();
 }
 }
 /* ================= EBNF =================================
 PROG = BaseList
 FOR = for (STMT; BEXP; STMT) BLOCK
 BLOCK = '{' BaseList '}'
 BaseList= { BASE }
 BASE = FOR | STMT;
 STMT = id '=' EXP | id '(' ArgList ')' | id OP1
 ArgList = EXP { ',' EXP }
 EXP = ITEM OP2 ITEM | ITEM
 BEXP = EXP BOP EXP
 */
 class SymbolTable : Dictionary<String, Object> 
 {
 }
 public class Interpreter
 {
 SymbolTable symbolTable = new SymbolTable();
 Tree parseTree;
 public Interpreter(Tree pTree)
 {
 parseTree = pTree;
 }
 public Object run()
 {
 return run(parseTree);
 }
 public Object run(Tree node)
 {
 if (node == null) return null;
 if (node.type.Equals("FOR")) // FOR = for (STMT; BEXP; STMT) BLOCK
 {
 Tree stmt1 = node.childs[2], bexp = node.childs[4], stmt2 = node.childs[6], block = node.childs[8];
 run(stmt1);
 while (true)
 {
 bool cond = (bool)run(bexp);
 if (!cond) break;
 run(block);
 run(stmt2);
 }
 }
 else if (node.type.Equals("STMT")) // id '=' EXP | id '(' ArgList ')' | id OP1
 {
 String id = node.childs[0].value;
 if (node.childs[1].type.Equals("="))
 {
 Tree exp = node.childs[2];
 Object rzExp = run(exp);
 symbolTable[id] = rzExp;
 return rzExp;
 }
 else if (node.childs[1].type.Equals("("))
 {
 StringBuilder argStr = new StringBuilder();
 Tree argList = node.childs[2];
 foreach (Tree arg in argList.childs)
 {
 if (!arg.type.Equals(","))
 {
 Object argObj = run(arg);
 argStr.Append(argObj);
 }
 }
 if (id.Equals("println"))
 Console.WriteLine(argStr.ToString());
 }
 else
 {
 String op1 = node.childs[1].value;
 int number = (int)symbolTable[id];
 if (op1.Equals("++"))
 number++;
 else if (op1.Equals("--"))
 number--;
 else
 Error.error("OP1 = " + op1 + " is not a valid operator !");
 symbolTable[id] = number;
 return number;
 }
 }
 else if (node.type.Equals("EXP") || node.type.Equals("BEXP")) // EXP = ITEM OP2 ITEM | ITEM // BEXP = EXP BOP EXP
 {
 Tree item1 = node.childs[0];
 Object o1 = run(item1);
 if (node.childs.Count == 1)
 return o1;
 else
 {
 int i1 = (int) o1;
 String op2 = node.childs[1].value;
 Tree item2 = node.childs[2];
 int i2 = (int) run(item2);
 if (op2.Equals("+"))
 return i1 + i2;
 else if (op2.Equals("-"))
 return i1 - i2;
 else if (op2.Equals("*"))
 return i1 * i2;
 else if (op2.Equals("/"))
 return i1 / i2;
 else if (op2.Equals("<"))
 return (i1 < i2);
 else if (op2.Equals("<="))
 return (i1 <= i2);
 else if (op2.Equals(">"))
 return i1 > i2;
 else if (op2.Equals(">="))
 return i1 >= i2;
 else if (op2.Equals("=="))
 return i1 == i2;
 else if (op2.Equals("!="))
 return i1 != i2;
 else
 Error.error("OP2 : " + op2 + " is not a valid operator !");
 }
 }
 else if (node.type.Equals("number"))
 return Int32.Parse(node.value);
 else if (node.type.Equals("string"))
 return node.value.Substring(1, node.value.Length - 2);// convert "string" into string
 else if (node.type.Equals("id"))
 return symbolTable[node.value];
 else
 {
 if (node.childs != null)
 foreach (Tree child in node.childs)
 run(child);
 }
 return null;
 }
 }
 public class Regexp
 {
 // 傳回 text 中符合正規表示式 pattern 的所有段落。
 public static List<String> matches(String text, String pattern, int groupId)
 {
 List<String> rzList = new List<String>();
 Match match = Regex.Match(text, pattern);
 for (int i = 0; match.Success; i++)
 {
 rzList.Add(match.Groups[groupId].Value);
 match = match.NextMatch();
 }
 return rzList;
 }
 // 類似 Linux 中的 grep 指令,印出比對成功的所有字串
 public static void grep(String fileName, String pattern, int groupId)
 {
 Console.WriteLine("=============grep(" + fileName + "," + pattern + "," + groupId + ")=============");
 String text = IO.fileToText(fileName);
 List<String> m = Regexp.matches(text, pattern, groupId);
 foreach (String s in m)
 Console.WriteLine(s);
 }
 }
 public class Error
 {
 public static void error(String msg)
 {
 IO.debug(msg);
 throw new Exception(msg);
 }
 }
 public class IO
 {
 // 讀取文字檔,以字串形式傳回。
 public static String fileToText(String filePath)
 {
 StreamReader file = new StreamReader(filePath);
 String text = file.ReadToEnd();
 file.Close();
 return text;
 }
 public static void debug(int level, String msg)
 {
 Console.WriteLine(STR.spaces(level) + msg);
 }
 public static void debug(String msg)
 {
 debug(0, msg);
 }
 }
 public class STR
 {
 static String spacesText = " ";
 public static String spaces(int n) { return spacesText.Substring(0, n); }
 // public static String spaces(int n) { return String.Format("{0:"+n+"}", ""); }
 public static bool isFoundAt(String pItem, String pItemList)
 {
 if (("|" + pItemList + "|").IndexOf("|" + pItem + "|") >= 0)
 return true;
 else
 return false;
 }
 }
 public class RegexScanner
 {
 public static List<String> scan(String text)
 {
 return Regexp.matches(text, "\".*?\"" + @"|(\d+)|([a-zA-Z]\w*)|([\+\-\*/<=>!]+)|([^\s])", 0); // 取得 數字串, 字元串, 或單一字元
 }
 }
 public class Tree // Abstract Syntax Tree
 {
 public String type = null;
 public String value = null;
 public List<Tree> childs = null;
 public Tree(String pType) { type = pType; }
 public Tree(String pType, String pValue) { type = pType; value = pValue; }
 public void addChild(Tree child)
 {
 if (childs == null)
 childs = new List<Tree>();
 childs.Add(child);
 }
 public static String toText(Tree tree, int level)
 {
 StringBuilder rzText = new StringBuilder();
 rzText.Append(STR.spaces(level));
 rzText.Append("+" + tree.type);
 if (tree.value != null)
 rzText.Append("\t = " + tree.value);
 rzText.Append("\n");
 if (tree.childs != null)
 {
 foreach (Tree child in tree.childs)
 rzText.Append(toText(child, level + 1));
 rzText.Append(STR.spaces(level) + "-" + tree.type + "\n");
 }
 return rzText.ToString();
 }
 public override String ToString()
 {
 return toText(this, 0);
 }
 }
 public class C3Parser
 {
 String text;
 List<String> tokens;
 List<String> types;
 int idx = 0;
 String KEYWORDS = "|if|for|while|";
 String OP1 = "++|--";
 String OP2 = "+|-|*|/";
 String BOP = "==|!=|<=|>=|<|>";
 String ITEM = "id|number|string";
 Stack<Tree> stack;
 StringBuilder toCodeText = new StringBuilder();
 public C3Parser(String pText)
 {
 text = pText;
 tokens = RegexScanner.scan(text);
 types = new List<String>();
 for (int i = 0; i < tokens.Count; i++)
 {
 String type = tokenToType(tokens[i]);
 types.Add(type);
 IO.debug("token[" + i + "] =\t" + tokens[i] + "\t" + type);
 }
 }
 public void error(String msg)
 {
 IO.debug("Error : token[" + idx + "]=" + tokens[idx]);
 IO.debug(" " + msg);
 throw new Exception(msg);
 }
 public String tokenToType(String token)
 {
 if (("|" + KEYWORDS + "|").IndexOf("|" + token + "|") >= 0)
 return token;
 else if (token[0] == '\"')
 return "string";
 else if (Char.IsDigit(token[0]))
 return "number";
 else if (Char.IsLetter(token[0]))
 return "id";
 else
 return token;
 }
 public bool isNext(String pTypes)
 {
 if (idx >= tokens.Count) return false;
 return STR.isFoundAt(types[idx], pTypes);
 }
 public String next(String pTypes)
 {
 if (isNext(pTypes))
 {
 // if (("|"+KEYWORDS+"|.|{|}|(|)|[|]|;|,|").IndexOf(types[idx])<0)
 addChild(types[idx], tokens[idx]);
 IO.debug(stack.Count, "token[" + idx + "] =\t" + tokens[idx] + "\t" + types[idx]);
 return tokens[idx++];
 }
 else
 {
 error("next token " + tokens[idx] + " is not in type:" + pTypes);
 return null;
 }
 }
 public Tree push(String pType)
 {
 IO.debug(stack.Count, "+" + pType);
 Tree tree = new Tree(pType);
 stack.Push(tree);
 return tree;
 }
 public Tree pop(String pType)
 {
 Tree tree = stack.Pop();
 IO.debug(stack.Count, "-" + tree.type);
 if (!tree.type.Equals(pType))
 error("pop type=" + tree.type + " should be " + pType);
 if (stack.Count > 0)
 stack.Peek().addChild(tree);
 return tree;
 }
 public Tree addChild(String pType, String pValue)
 {
 Tree child = new Tree(pType, pValue);
 stack.Peek().addChild(child);
 return child;
 }
 public Tree parse()
 {
 IO.debug("================= Parse Begin =================");
 stack = new Stack<Tree>();
 Tree progTree = new Tree("PROG");
 stack.Push(progTree);
 parseBaseList();
 IO.debug("================= Parse Tree ===============");
 IO.debug(progTree.ToString());
 if (stack.Count == 1)
 return stack.Pop();
 else
 {
 error("parse fail : stack.count = " + stack.Count);
 return null;
 }
 }
 // FOR = for (STMT; BEXP; STMT) BLOCK
 public void parseFor()
 {
 push("FOR");
 next("for");
 next("(");
 parseStmt();
 next(";");
 parseBexp();
 next(";");
 parseStmt();
 next(")");
 parseBlock();
 pop("FOR");
 }
 // BLOCK = '{' BaseList '}'
 public void parseBlock()
 {
 push("BLOCK");
 next("{");
 parseBaseList();
 next("}");
 pop("BLOCK");
 }
 // BaseList= { BASE }
 public void parseBaseList()
 {
 push("BaseList");
 while (idx < tokens.Count && !isNext("}"))
 parseBase();
 pop("BaseList");
 }
 // BASE = FOR | STMT;
 public void parseBase()
 {
 push("BASE");
 if (isNext("for"))
 parseFor();
 else
 {
 parseStmt();
 next(";");
 }
 pop("BASE");
 }
 // STMT = id '=' EXP | id '(' ArgList ')' | id OP1
 public void parseStmt()
 {
 push("STMT");
 next("id");
 if (isNext("=")) // id '=' EXP --> ASSIGN
 {
 next("=");
 parseExp();
 }
 else if (isNext("(")) // id '(' ArgList ')' --> Function Call
 {
 next("(");
 if (!isNext(")"))
 parseArgList();
 next(")");
 }
 else // id OP1
 next(OP1);
 pop("STMT");
 }
 // ArgList = EXP { ',' EXP }
 public void parseArgList()
 {
 push("ArgList");
 parseExp();
 while (isNext(","))
 {
 next(",");
 parseExp();
 }
 pop("ArgList");
 }
 // EXP = ITEM OP2 ITEM | ITEM
 public void parseExp()
 {
 push("EXP");
 next(ITEM);
 if (isNext(OP2))
 {
 next(OP2);
 next(ITEM);
 }
 pop("EXP");
 }
 // BEXP = EXP BOP EXP
 public void parseBexp()
 {
 push("BEXP");
 parseExp();
 next(BOP);
 parseExp();
 pop("BEXP");
 }
 }
}

作者

陳鍾誠,於金門大學資訊工程系,電子郵件:wt.ude.uqn|ccc#wt.ude.uqn|ccc,網站:http://ccckmit.wikidot.com。

授權

本文採用創作共用 (Creative Common) 3.0 版的 姓名標示─非商業性─相同方式分享 授權條款,歡迎轉載或修改使用,但若做為商業使用時必須取得授權,引用本文時請參考下列格式。

中文版 (APA格式)

陳鍾誠 (28 Sep 2009 01:42),(網頁標題) 如何自己動手設計解譯器,(網站標題) 陳鍾誠的網站,取自 http://ccckmit.wikidot.com/code:interpreter ,網頁修改第 7 版。

英文版 (APA格式)

Chung-Chen Chen (28 Sep 2009 01:42), Retrieved from http://ccckmit.wikidot.com/code:interpreter , Page Revision 7.