如何自己動手設計解譯器

程式作品

C 語言

Java

C＃

JavaScript

常用函數

文字處理

遊戲程式

衛星定位

系統程式

資料結構

網路程式

自然語言

人工智慧

機率統計

資訊安全

等待完成

訊息

相關網站

參考文獻

最新修改

簡體版

English

程式專案下載：Interpreter.zip

簡介

解譯器 (Interpreter) 是用來執行程式語言的一種程式，本文目的在示範如何設計一個簡單的解譯器，為了簡化起見，我們將 C 語言的語法簡化，形成一個小型語言，稱為 C0 。舉例而言，以下程式 test99.c0 就是一個 C0 語言的程式範例。

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

實作

我們利用 C# 語言設計出 C0 語言的解譯器，其程式碼如下所示。

// ------------------ 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");
        }
    }
}

Facebook
c#code
page revision: 7, last edited: 19 Oct 2010 09:08
Edit Rate (0) Tags Discuss (0) History Files Print Site tools + Options
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License