# 編譯器期末Proposal
###### tags: `Compiler Design`

# Parsing statement list program using flex and bison


> [Parsing statement list program using flex and bison](https://ieeexplore.ieee.org/document/8298547)

## Abstract
#### 名詞解釋:
* Static Program Analyse = 在非執行階段(execution time)所進行的分析

#### 主要好處:
* 用於檢驗safety critical systems的正確性並提高軟體工程師的開發效率

#### 目前應用

* Static Program Analyse已逐漸用於IEC 61131-3的PLC程序( PLC programs based on IEC 61131-3)

#### 瓶頸與目標

* 因為其無法適應大多廠商的專有語言(most of the proprietary languages used by vendors)，因此我們希望提出一個通用的方法(a general approach is proposed)

#### 方式
* 使用flex與bison來自動產生(automatically generate)用於STL program的Parser

> [The C++ Standard Template Library (STL)](https://www.geeksforgeeks.org/the-c-standard-template-library-stl/)

#### 驗證

* 以Siemens Company的STEP7 STL作為驗證(verified by an example of STEP7 STL from Siemens)
> [Siemens Company](https://www.siemens.com/global/en.html)

#### 額外補充

介紹關於STL在Static Program Analysis的Front-end的Sementic(語意)階段會遇到的問題、解法與有效的實作(effectively implementing)

# SECTION I: Introcduction
### standard IEC 61131-3 standardized programming language的開發原因
為了統一可編程邏輯控制器(programmable logic controllers)所使用的不同語言以及改善效能與工業應用的開發成本，所定義用於PLC programs的標準化編程語言(standardized programming language)

> [What is a PLC?](https://inductiveautomation.com/resources/article/what-is-a-PLC)

### IEC 61131-3標準立定與後續發展
在此標準發布後便成為後續PLC程式的主要依準，並且也發展出許多由IEC 61131-3延伸的分析工具。但基於實際原因(practical reasons)，每家PLC供應商(vendor)在語言上所提供的方言(dialect)會有些微不同，有時甚至同一家供應商會提供不同的產品。因此我們不能直接將IEC 61131-3直接使用。

### 本篇論文提供

藉由使用STEP7 STL from Siemens來說明本文提供的一個通用方法(general approach)

### STL 介紹與瓶頸
STL = Statement List，是用於Siemens STEP7 PLC controllers的程式上，是一種IEC 61131-3所描述的指令式列表語言(Instruction List language)的推導，也是一個assembly-level的proprietary structural language。而他在語義(semantic)上的複雜與私有性也使得其分析更為困難。

> [Instruction List (IL) Language](https://product-help.schneider-electric.com/Machine%20Expert/V1.1/en/SoMProg/SoMProg/FBD_LD_IL_Editor/FBD_LD_IL_Editor-6.htm)

> [SIMATIC Statement List (STL) for S7-300 and S7-400 Programming ](https://cache.industry.siemens.com/dl/files/814/109751814/att_933093/v1/STEP_7_-_Statement_List_for_S7-300_and_S7-400.pdf)

### 主題聚焦
* 本文著重:STL static analysis中front-end的部分
* 過程方式:使用flex與bison進行parsing
* 期望目標:分析STL語言的語義(semantic)，並且將其翻譯為沒有額外負擔(side effect)的中間語言(IR，intermediate representation)以達到效能實現的目標

### 其餘章程規畫
* Section II:概述static program analysis中的front-end行為
* Section III:使用flex, bison自動生產STL program parser的的實作方式說明
* Section IV:分析STL 程式中的side effect與提出將其轉譯為IR的解法
* Section V:結論探討

# SECTION II: System Overview
## 概述static program analysis中的front-end行為

相比從前從頭設計一個scanner 與parser，現代主流(mainstream)更趨向使用諸如flex,bison等scanner, parser generator的方式，scanner與parser以Backus-Naur-Form的方式倂接在一起(formal grammar in Backus-Naur-Form)

> [Backus-Naur Form](https://www.sciencedirect.com/topics/computer-science/backus-naur-form)

#### Overall Structure for the front end of the static program analysis


> Fig. 1, Framework of the front-end

> 111學年下學期，編譯器課程講義補充

# SECTION III: Parsing Source File of STL Program
## 使用flex, bison自動生產STL program parser的的實作方式說明

## A. Lexical Analysis
### Lexical Analysis，編譯器課程補充
#### 概念
1st Phase: Lexical Analysis(辭彙分析)，Scanning
* 同義詞: analysis/ scanning/ lexing/ tokenization(把string 切為 **tokens**)
* 定義: Look words up in the dictionary. 需要檢查有無存在於字典(**Dictionary**)內

| in Analogy to English | Syntax Analysis Example |
| -------- | -------- |
| | |

* Examlpe

由範例可知，Lexical主旨在"Tokenize"，我們可以將position的公式對照**Symbol Table**(符號表)切分為對應<id,1> <=> <id,2> <+> <id,3> <＊> <60>，其中id為**identifier**(辨認字)的縮寫

#### Lex Part


> Lex:First Section

> Lex:Second Section

> Lex:Third Section

#### Yacc Part

#### flex and bison Structure

> flex and bison structure

### 回歸文本
Lexical analysis是一種將character stream轉變為token sequences的程序。在本程序中我們使用flex來產生一個scanner。

> flex檔案示意

由上圖可知，一個flex程式會由`%%`符號切割為三部分:
* first section: declarations and option settings
* second section: 系列的lexical rules
* third section: user code，且將會被複製到生成的scanner中以關聯將執行的動作

原則上，我們在將對所有Second section提到規則的terminals進行編碼，下述一個簡易的lexical結構

#### Pattern Action
在所有規則中，我們會將Pattern描述為正規表示式(regular expression)，並且當pattern matching時將執行對應C code，並且除了將id回傳給parser，scanner還會執行額外動作，諸如:回傳pattern確切對應的character stream。

> Second Section rules: regular expression

## B. Backus-Naur-Form
為了產生一個parser用來將一串token轉為syntax tree，我們需要用一些方式來描述規則，而context-free grammar (CFG)是parsers handle最常使用的一種語言。而CFG的正式標準寫法稱為Backus-Naur Form(BNF)

BNF由production rules是一種metalinguistic formulas 包含了 metalinguistic 變數(variables),連接詞(connectives),terminals,expressions，而他的拆分以`<>`包含每個metalinguistic單位
> [Exact meaning of metalinguistic variable](https://cs.stackexchange.com/questions/119175/exact-meaning-of-metalinguistic-variable)

且每個production rule會以`=`左邊作為expression，右邊作為metalinguistic variable。且使用`|`作為選擇連接詞。

## C. Syntax Analysis
在BNF表示法中，bison在由flex所生成的scanner的輔助下，產生一個可以parse character stream的parser

而建立在S7 PLC的STL program實作可以分為以下四個部分

1. Organization Block(OB): 作為OS與user間的介面，用於管理scan cycle, interrupt execution, 以及PLC與error handling的起始時間
2. Function Block(FB):是一個有固定進入與離開點，user可使用的區域。每個FB都有自己的local memory，且與stack memory不同的是每個FB的local memory皆存在於相同的絕對路徑。
3. Function(FC):FC與FB不同的地方在與她沒有自己的local memory，且他將temp variables儲存於stack memory中
4. Data Block(DB):DB儲存Blocks關於physical process的配置資訊。而有一種特殊的DB，instance DB是為了傳遞參數給FB

根據不同的需求，使用者可以選擇blocks或specific blocks。且因為STL並沒有適當的參考文件，我們將用分析STL building blocks的方式來學習其general structure

每個Block可以被分為三部分
1. program declarations, < ProgDec >
2. variable declarations, < VarDec >
3. STL instructions, < Instructions >

> Definition 1: Structure of STL Program

每個block需要由program declaration作為開頭，隨後可以連接optional parameters(像是 title, author, family等等)

在production rule第一個空白符號前的符號`|`代表沒有額外的non-terminals需要被分割，而"LF"則代表換行符號

> Definition 2: Grammar for Program Declaration

每個在building block中使用的變數都需要在program declaration被宣告，包含 input, output variable, temporary, static and input /output variable。且每個變數種類都有獨立的部分可供使用。並且，變數可以不具有初始值，但一定要有data type

> Definition 3: Grammar for Variable Declarations

經過上述步驟後，我們完成了部分的STL描述，且這部分會由如 BEGIN, NETWORK, TITLE的關鍵字作為開頭、並由代表結束(indicated to end)的關鍵字作為結尾

指令有可能經由jump從代表program的control flow的label處開始，並且在特定情況下可由jump來跳轉到有前綴(prefixed)的指令來達成指令的跳躍。且程式會繼續由label前綴進行。

且在label中，指令會由operand(通常是在variable declarations中以宣告，用於parameterize the operator的變數)作為開頭，並在之後會是另一個notation前以分號(semicolon)作為結束

且因為大量的operators會導致Parser效能降低，因此我們將對operators進行分類，用以有效降低terminals的數量進而改善效能。該Grammer展示如下圖

> Definition 4: Grammar for STL Instructions

# SECTION IV: Translating STL Program to Intermediate Representation
## 分析STL 程式中的side effect與提出將其轉譯為IR的解法

在前述的步驟中，我們將STL的Source file以 lexical analysis and syntax analysis的方式轉為abstract syntax tree，儘管如此，STL source code仍尚不適用static analysis的方式，因此我們需要將其轉為中間語言(IR,intermediate representation)。

PLCs有許多不同的硬體暫存器，我們將選擇其中兩種特別關乎於side effects暫存器
1. accumulators
2. status word

#### accumulators
accumulators是執行STL指令的關鍵組件，幾乎所有的指令皆使用他來執行。雖然在不同的PLC型號間會有相異數量的accumulators，但我們以兩個32-bit accumulators 作為分析STL program的範例

#### status word
status word是一個16-bit wide register，且其中只有九種state用於執行指令後的store、result與errors。

> Fig. 2.Description of the status word

而當指令修改到註記符(instruction's mnemonic)未提及的processor state時，我們稱一個該指令具有side effect。以下提供一個hidden side effect的典型案例，例如arithmetic instruction隱藏式修改條件(implicitly modifies conditional codes)且他明顯連帶改動到了暫存器

Side effects也可能掩蓋特定control flow使program static analysis更為困難。因此，我們介紹了IR作為分析的基底。IR建構在四元(quadruple)下，廣泛用於編譯器中。

> general structure of quadruple

出於篇幅考慮，將省略IR的詳細介紹

## A. Bit Logic Instructions
Bit Logic Instructions使用RLO作為input register且會將結果存於同樣的暫存器中

> The conversion of the assignment instruction results in IR

## B. Load and Transfer Instructions
### load instruction
包含兩個assignments

> load instruction

1. assign the content of ACCU 1 to ACCU 2
2. assign the content of operand to ACCU 1

### transfer instruction

> transfer instruction

assigns values of ACCU 1 to the operand

## C. Arithmetic Instructions
Arithmetic instructions包含了integer, floating arithmetic, word logical instructions。這些指令在RLO上部會進行任何事，但會影響state CC1, CCO, OV, OS與兩個accumulators

> The conversion of the arithmetic instruction +1 results in IR

## D. Jump Instructions
Jump instructions密切相關於status word，除了無條件跳躍指令( unconditional jump instruction)外，也交互影響 status RLO, BR, OV, OS, CC0 與 CC1

> The conversion of the jump instruction JUO results in IR

## E. Compare Instructions
compare instructions用於比較相同型別的ACCU 2與ACCU 1，並且將結果儲存於RLO中。此外，compare的操作還影響了OV、CC1和CC0得顯示結果

> The conversion of the compare instruction>I results in IR

# SECTION V: Conclusion

本篇Paper展示了應用於Siemens STL program，parsing PLC program 的 general approach。是為了處理static analysis的預先準備步驟。對於STL的語意分析、將PLC Program轉換為IR也使專用於PLC的程式語言的static analysis應用更加容易，使得IR可照計畫進行下一步的轉換。