《編譯原理》中LR(0)語法分析動態演示系統分析與設計

石鳳貴

摘要：《編譯原理》課程是高校計算機專業一門核心專業課，培養學生熟悉編譯程序的內部結構及原理，為從事軟件開發奠定基礎，從而提升軟件人員的素質和能力。LR（0）分析是構造其他LR分析器的基礎。該文介紹了LR（0）語法分析可視化動態演示系統的分析與設計。

關鍵詞：編譯原理;LR（0）;文法

中圖分類號：TP311

文獻標識碼：A

文章編號：1009-3044（2020）03-0083-02

1 背景

《編譯原理》是高等學校計算機專業的一門必修課，理論性比較強，主要介紹程序設計語言翻譯的原理、技術及實現。計算機只能識別0和1所構成的指令序列，高級計算機語言編寫的程序不能直接在機器上運行，需要將源程序轉換為等價的目標程序，這個轉換過程就是編譯。從源程序到目標程序轉換的過程就是編譯過程，過程比較復雜，需要劃分為多個階段將源程序由一種表現形式轉換為另一種形式，每個階段的操作在邏輯上是緊密相連的。編譯過程分為六個階段（如圖1所示）：

2 LR（0）

LR（0）是一種“移進一規約”自底向上的分析文法，當棧頂符號串形成句柄時就采取規約，因此這種分析方法的關鍵是如何確定句柄。LR（k）分析方法是1965年Knuth提出的，參數k表示向右查看輸入串符號的個數。

LR（0）分析器由總控程序、分析表或分析函數、分析棧3個部分組成，其工作過程如圖2所示[1]。

LR（0）分析實例：

A.對文法G的產生式編號：

（0）S-→E （4）A→d

（1） E→Aa

（5）B→Cb

（2） E→Bb

（6）B→d

（3） A→Ca

B.構造這個文法的LR（O）分析表（如表1）[2][3]：C.對字符串bccd#用LR（O）分析器進行分析（如表2）：

3 系統總體設計

3.1 系統功能分析

本系統完成了對編譯原理相關知識的基本操作，采用人機交互界面，有一定的規范性，操作方便，比較直觀。主要功能有：

1）新建窗口，用于創建新的工程，也可打開演示工程。

2）在主窗口（一個類似VC的界面）中，可以編輯文法和源文件，系統并根據格式標準檢查輸入文檔是否有錯，若出錯則產生提示。

3）生成對應文法的分析表和狀態機，并可以對狀態機進行顯示類型的操作。

4）利用對應文法的分析表對相應的源文件進行動態分析，在這里顯示四個窗口——語法樹、源文件、堆棧、分析表，還可以進行單步顯示，這樣利于觀察其變化;還可以通過窗口操作對窗口進行“層疊”“平鋪”等操作。

3.2系統功能模塊框圖

3.3系統總體流程圖

4 系統詳細設計

4.1 生成LR（O）狀態機的程序流程圖

4.2 LR（O）分析過程程序流程圖

參考文獻：

[1]姜淑娟，張辰，劉兵.編譯原理及實現[M].北京：清華大學出版社，2016.

[2]康慕寧，林奕，編譯原理[M].北京：人民郵電出版社，2010.

[3]黃賢英，王柯柯，曹瓊，編譯原理及實踐教程[M].北京：清華大學出版社，2019.