内容目录

基于llvm的编译器设计与实现

在文法部分因为markdown引擎不同导致渲染效果不同，在网页下存在阅读困难，需要详细查看文法部分相关内容的建议前往项目处

简述

本文旨在说明课程实践大作业相关情况，主要涉及选用工程架构，必要的环境说明和配置，项目结构说明，代码说明等内容

对于部分超出编译原理的内容不会过多阐释，但会尽力对这些内容给出部分介绍和相关链接到所撰写的其他相关文章，希望能解决至少一部分疑问，同时对于文笔不足部分，和因精力有限无法详尽说明的内容或者因学疏才浅致使理论可能有缺陷的地方也恳请理解

项目使用c++基于llvm，即指使用llvm提供相关组件设计前端并使用llvm作为后端，设计了完成对指定语言完成编译工作的编译器，主要涵盖的工作包含词法分析、语法分析、语义分析、和IR生成。

编译器总体工作流程因此可划分为前端和后端，并分别简要概述

编译器前端工作流程如下：

从源语言进行词法分析 ——> 语法分析 ——> 语义分析 ——> 生成IR

后端由LLVM负责，可能经历的流程如下：

汇编 ——> 链接 ——> 目标代码生成

对于IR部分还可以存在IR优化部分，完整工作流程可参考下图：

Figure 1 编译器工作流程概览

对于前端部分做进一步说明，词法分析部分负责将源语言切分为所定义的不同token，并作为输入进入语法分析器进行语法分析；对于语义分析则是针对定义的语言构建抽象语法树保存相关语义信息，虽理论上将语法分析和语义分析明确划分开，但实际语义分析部分和语法分析部分同步进行难以分离，在语法分析的过程中便需要保存语义信息；再然后根据抽象语法树完成IR生成工作。至此完成了全部前端工作。

最后，关于课程实践大作业要求，下载链接如下，供参考：

“https://williamsfile.oss-cn-shanghai.aliyuncs.com/document/compileconcepts/编译实践大作业要求.docx”

如若涉及相关问题，将删除文件，届时请注意链接将失效

文法定义

原始定义

下面是用EBNF描述的L24语言，是预计实现语言的原始定义：

\ = "main" "{" \ "}"

\ = {\ ";"}

\ = \ | \ | \ | \ | \

\ = \ "=" \

\ = "if" "("\")" "then" "{"\"}" "end" | "if" "(" \ ")" "then" "{"\"}" "else" "{"\"}" "end"

\ = "while" "("\")" "{"\"}"

\ = "scan" "(" \ { "," \} ")"

\ = "print" "(" \ { "," \} ")"

\ = \ ( "==" | "!=" | "<" | "<=" | ">" | ">=" ) \

\ = [ "+" | "-" ] \ { ( "+" | "-" ) \ }

\ = \ { ( "***" | "/**" ) \ }

\ = \ | \ | "(" \ ")"

注：

所有的终结符均加粗并用双引号括起表示。
该语言中的标识符都是简单的整型变量；它通过出现在assign_stmt语句左边来隐式地声明一个变量。变量的作用域是全局的。
相关符号定义同清华大学出版社《编译原理》(第3版) (王生原，董渊等著) p13定义

拓展后定义

在拓展过程调用、多维数组、for语句和++、--运算符后，扩展后L24语言如下：

<program> = { "procedure"   <ident>  "("   <ident>  {  ","  <ident>  }   ")"    "{"     <stmt_list>   "return"    <ident>       ";"  "}"  }   "main" "{" <stmt_list> "}"

<stmt_list> = {<stmt> ";"}

<stmt> = <assign_stmt> | <if_stmt> | <while_stmt> | <scan_stmt> | <print_stmt> ｜ <for_stmt>

<assign_stmt> = <ident> "=" <expr> 

<if_stmt> = "if" "(" <bool_expr> ")" "then" "{" <stmt_list> "}" "end" | "if" "(" <bool_expr> ")" "then" "{" <stmt_list> "}" "else" "{" <stmt_list> "}" "end"

<while_stmt> = "while" "(" <bool_expr> ")" "{" <stmt_list> "}"

<scan_stmt> = "scan" "(" <ident> { "," <ident>} ")" 

<print_stmt> = "print" "(" <expr> { "," <expr>} ")"

<for_stmt> = "for" "(" <assign_stmt> ";" <bool_stmt> ";"  <expr>  ")" "{" <stmt_list> "}"

<bool_expr> = <expr> ( "==" | "!=" | "<" | "<=" | ">" | ">=" ) <expr>

<expr> = [ "+" | "-" ] <term> { ( "+" | "-" ) <term> } 

<term> = <factor> { ( "*" | "/" ) <factor> }

<factor> = { "++" | "--" } <ident> { <array_ref> }    | <ident> { <array_ref> } { "++" | "--" } | <number> | "(" <expr> ")"   | <ident>  "("   <ident>    {      ","       <ident>          }     ")"

<array_ref> = "["   <number>   "]"    {     "["   <number>   "]"      }

<ident> = 字符串

<number>  =   数字串

同时可以参考项目中根目录下rule.md文件给出了较为详尽的规则

亦附上上述相关规则

文法规则

<program>       :   <procedure_declare>  main    {       <stmt_list>     }

<procedure_declare> :   procedure   <ident>     (    <ident>    <args_list>    )    {    <stmt_list>   return   <ident>   ;  } <procedure_declare>

<procedure_declare> :   null

<args_list>     :   ,   <ident>     <args_list>

<args_list>     :   null

<stmt_list>     :   <stmt>  ;   <stmt_list>

<stmt_list>     :   null

<stmt>          :   <assign_stmt>

<stmt>          :   <if_stmt>

<stmt>          :   <while_stmt>

<stmt>          :   <for_stmt>

<stmt>          :   <scan_stmt>

<stmt>          :   <print_stmt>

<assign_stmt>   :   <ident>     =       <expr>

<if_stmt>       :   if  (       <bool_expr>     )   then    {   <stmt_list>    }    <else_stmt>

<else_stmt>     :   end

<else_stmt>     :   else    {   <stmt_list>    }    end

<while_stmt>    :   while   (       <bool_expr>     )       {     <stmt_list>      }

<for_stmt>      :   for     (     <assign_stmt>     ;       <bool_stmt>      ;       <expr>      )      {    <stmt_list>    }

<scan_stmt>     :   scan    (       <ident>     <scan_args>

<scan_args>     :   ,       <ident>     <scan_args>

<scan_args>     :   )

<print_stmt>    :   print    (       <expr>     <print_args>

<print_args>    :   ,       <expr>     <print_args>

<print_args>    :   )

<bool_expr>     :   <expr>  <bool_condition>

<bool_condition>:   ==  <expr>

<bool_condition>:   !=  <expr>

<bool_condition>:   <   <expr>

<bool_condition>:   <=  <expr>

<bool_condition>:   >   <expr>

<bool_condition>:   >=  <expr>

<expr>          :   <prefix_term>   <term>  <expr_term>

<expr>          :   <term>  <expr_term>

<expr_term>     :   +   <term>  <expr_term>

<expr_term>     :   -   <term>  <expr_term>

<expr_term>     :   null

<prefix_term>   :   +

<prefix_term>   :   -

<term>          :   <factor>    <term_factor>

<term_factor>   :   *   <factor>    <term_factor>

<term_factor>   :   /   <factor>    <term_factor>

<term_factor>   :   null

<factor>        :   <increment_preop>   <ident>   <array_ref>

<factor>              :       <ident>       <proceorid>

<factor>        :   <number>

<factor>        :   (    <expr>    ) 

<proceorid>           :       <array_ref>   <increment_op>

<proceorid>           :   (   <ident>     <procedure_args>    )

<array_ref>     :   [     <number>    ]     <array_ref>

<array_ref>     :   null

<procedure_args>:   ,   <ident>     <procedure_args>

<procedure_args>:   null

<increment_preop>:    ++

<increment_preop>:    --

<increment_op>  :   ++

<increment_op>  :   --

<increment_op>    :       null

<ident>         :   字符串

<number>        :   数字串

可以计算相关FIRST集、FOLLOW集和SELECT集，并验证是LL(1)文法，此部分不作详细计算，但列出较为相关的SELECT集以供核验，并为后续实现作铺垫

SELECT集计算

\

SELECT(\ ——> procedure \ ( \ \ ) { \ return \ ; } \) = { procedure }

SELECT(\ ——> $\varepsilon$ ) = { main }

\

SELECT(\ ——> , \ \) = { , }

SELECT(\ ——> $\varepsilon$ ) = { ) }

\

SELECT(\ ——> \ ; \) = { if, while, for, scan, print, 字符串 }

SELECT(\ ——> $\varepsilon$ ) = { } }

\

SELECT(\ ——> \) = { 字符串 }

SELECT(\ ——> \) = { if }

SELECT(\ ——> \) = { while }

SELECT(\ ——> \) = { for }

SELECT(\ ——> \) = { scan }

SELECT(\ ——> \) = { print }

\

SELECT(\ ——> end ) = { end }

SELECT(\ ——> else { \ } end) = { else }

\

SELECT(\ ——> , \ \) = { , }

SELECT(\ ——> ) ) = { ) }

\

SELECT(\ ——> , \ \) = { , }

SELECT(\ ——> ) ) = { ) }

\

SELECT(\ ——> == \) = { == }

SELECT(\ ——> != \) = { != }

SELECT(\ ——> < \) = { < }

SELECT(\ ——> \<= \) = { <= }

SELECT(\ ——> > \) = { > }

SELECT(\ ——> >= \) = { >= }

\

SELECT(\ ——> \

\ \) = { +, - }

SELECT(\ ——> \ \) = { ++, --, 数字串, 字母串, ( }

\

SELECT(\ ——> + \ \) = { + }

SELECT(\ ——> - \ \) = { - }

SELECT(\ ——> $\varepsilon$ ) = { ==, !=, <, <=, >, >=, ), ,, ; }

\

SELECT(\ ——> +) = { + }

SELECT(\ ——> -) = { - }

\

SELECT(\ ——> \ \) = { }

SELECT(\ ——> / \ \) = { / }

SELECT(\ ——> $\varepsilon$ ) = { +,- }

\

SELECT(\ ——> \ \ \ ) = { ++, -- }

SELECT(\ ——> \ \ ) = { 字符串 }

SELECT(\ ——> \) = { 数字串 }

SELECT(\ ——> ( \ ) ) = { ( }

\

SELECT(\ ——> \ \) = { [, ++, --, *, /, +, -, ,, ), ; }

SELECT(\ ——> ( \ \ )) = { 字符串 }

\

SELECT(\ ——> [ \ ] \) = { [ }

SELECT(\ ——> $\varepsilon$ ) = { ++, --, *, /, +, -, ,, ), ;, ==, !=, <, <=, >, >= }

\

SELECT(\ ——> , \ \) = { , }

SELECT(\ ——> $\varepsilon$ ) = { ) }

\

SELECT(\ ——> ++) = { ++ }

SELECT(\ ——> --) = { -- }

\

SELECT(\ ——> ++) = { ++ }

SELECT(\ ——> --) = { -- }

SELECT(\ ——> $\varepsilon$ ) = { *, /, +, -, ,, ), ;, ==, !=, <, <=, >, >= }

LLVM概述

LLVM（Low Level Virtual Machine）是一个用于编译器开发的开源框架，提供了一个高度模块化和可扩展的编译器架构，能够支持多种编程语言和目标平台

llvm组成如下：

LLVM核心库-提供编译器的基础设施，包括中间表示（IR）、优化器和代码生成器。LLVM IR是一种与机器无关的中间表示语言，可以在编译期间进行各种优化。
Clang-一个基于LLVM的C语言家族编译器前端，支持C、C++和Objective-C等语言。Clang提供了优越的诊断信息和高性能的编译速度。
LLVM优化器-包括一系列的优化通道和策略，可以对LLVM IR进行静态分析和优化，以提高代码的执行效率。
代码生成器-能够将LLVM IR转换为目标平台的机器代码。LLVM支持多种架构，包括x86、ARM、PowerPC等。
LLC-LLVM的链接器，能够快速地链接目标文件并生成可执行文件或库文件。
LLDB-基于LLVM的调试器，支持多种编程语言的调试功能，特别是对C/C++和Objective-C的支持非常完善。
Libc++：一个符合C++标准的标准库实现，与LLVM和Clang紧密集成，提供高效和现代化的C++标准库功能。

llvm本身是一个较大的概念，因此可以有多个定义。此处llvm尤其指代使用llvm核心库编写的编译器前端。

环境说明及配置

环境说明

操作系统：MacOS
指令架构：X86
编程语言：C++
其他环境配置：git，cmake，make，ninja，llvm，nginx，php

环境配置

环境配置方面仅说明与编译器相关配置，采用源码方式编译安装llvm，操作系统为MacOS

主要使用homebrew安装相关工具

brew install make git cmake ninja

可采用以下命令检查版本

brew list --version make git cmake ninja

前往自定义的下载目录使用git克隆llvm

git clone https://github.com/llvm/llvm-project.git

编译安装llvm

cd llvm-project
mkdir build
cd build
cmake -G Ninja -DCMAKE_BUILD_TYPE=Debug -DLLVM_ENABLE_PROJECTS=clang ../llvm

ninja

可使用一下命令测试

ninja check-all

安装llvm

sudo ninja install

可使用以下命令验证llvm是否正确安装

llc --version

若安装正确，则命令行回显内容如下：

LLVM (http://llvm.org/):
  LLVM version 19.0.0git
  DEBUG build with assertions.
  Default target: x86_64-apple-darwin21.6.0
  Host CPU: skylake

  Registered Targets:
    aarch64     - AArch64 (little endian)
    aarch64_32  - AArch64 (little endian ILP32)
    aarch64_be  - AArch64 (big endian)
    amdgcn      - AMD GCN GPUs
    arm         - ARM
    arm64       - ARM64 (little endian)
    arm64_32    - ARM64 (little endian ILP32)
    armeb       - ARM (big endian)
    avr         - Atmel AVR Microcontroller
    bpf         - BPF (host endian)
    bpfeb       - BPF (big endian)
    bpfel       - BPF (little endian)
    hexagon     - Hexagon
    lanai       - Lanai
    loongarch32 - 32-bit LoongArch
    loongarch64 - 64-bit LoongArch
    mips        - MIPS (32-bit big endian)
    mips64      - MIPS (64-bit big endian)
    mips64el    - MIPS (64-bit little endian)
    mipsel      - MIPS (32-bit little endian)
    msp430      - MSP430 [experimental]
    nvptx       - NVIDIA PTX 32-bit
    nvptx64     - NVIDIA PTX 64-bit
    ppc32       - PowerPC 32
    ppc32le     - PowerPC 32 LE
    ppc64       - PowerPC 64
    ppc64le     - PowerPC 64 LE
    r600        - AMD GPUs HD2XXX-HD6XXX
    riscv32     - 32-bit RISC-V
    riscv64     - 64-bit RISC-V
    sparc       - Sparc
    sparcel     - Sparc LE
    sparcv9     - Sparc V9
    systemz     - SystemZ
    thumb       - Thumb
    thumbeb     - Thumb (big endian)
    ve          - VE
    wasm32      - WebAssembly 32-bit
    wasm64      - WebAssembly 64-bit
    x86         - 32-bit X86: Pentium-Pro and above
    x86-64      - 64-bit X86: EM64T and AMD64
    xcore       - XCore

其他环境包括nginx，php等可参考“LAMP/LNMP环境搭建“：https://williamshen.cn/wordpress/?p=10
在其他Linux环境下可考虑采用yum，dnf等替代homebrew配置环境

项目结构说明

根目录下项目结构如下：

.
├── Makefile
├── build
│   ├── bin
│   │   ├── irgenerator_test
│   │   ├── lexer_test
│   │   ├── main
│   │   └── parser_test
│   ├── obj
│   │   ├── irgenerator.o
│   │   ├── irgenerator_test.o
│   │   ├── lexer.o
│   │   ├── lexer_test.o
│   │   ├── main.o
│   │   ├── parser.o
│   │   └── parser_test.o
│   └── output
│       ├── output
│       ├── output.ll
│       └── output.o
├── include
│   ├── irgenerator_interface.hpp
│   ├── lexer_interface.hpp
│   └── parser_interface.hpp
├── main.cpp
├── rule.md
├── simplecompiler
│   ├── build
│   │   └── output
│   ├── compile.php
│   ├── index.php
│   ├── main
│   └── tmpcode
├── src
│   ├── AST
│   │   └── AST.hpp
│   ├── IRgenerator
│   │   ├── IRgenerator.cpp
│   │   ├── IRgenerator.hpp
│   │   └── IRgenerator_test.cpp
│   ├── Makefile
│   ├── lexer
│   │   ├── lexer.cpp
│   │   ├── lexer.hpp
│   │   └── lexer_test.cpp
│   ├── parser
│   │   ├── parser.cpp
│   │   ├── parser.hpp
│   │   └── parser_test.cpp
│   └── semanticanalyzer
├── start.sh
├── test.sh
└── test_codes
    ├── array.txt
    ├── array2.txt
    ├── basic.txt
    ├── procedure_simcal.txt
    └── procedure_withoutscan.txt

根目录下各文件说明如下：

Makefile
- 项目采用Makefile编译，基本使用方法使用make命令编译编译器主程序，内部定义了项目编译细节
- src目录下同样定义了Makefile作为子Makefile完成目标代码生成，父Makefile调用子Makefile编译并按任务汇总所需目标代码链接成为可执行文件
main.cpp
- 编译器主程序main
rule.md
- 定义语言的规则
start.sh
- 运行编译器主程序main的shell脚本，内部定义了一系列回显信息便于交互，具体请查看“运行方式”一节
test.sh
- 同start.sh，但用于相关程序测试

各文件夹说明如下：

build

build目录用于存储项目编译过程中所产生的中间文件和最终可执行文件，包含bin，obj和output，具体编译规则详见makefile

bin

bin目录存储生成的可执行文件，项目中将包括以下可执行文件

lexer_test -- 词法分析器测试
parser_test -- 语法分析器测试
irgenerator_test -- llvm IR生成器测试
main -- 编译器主程序

obj

obj目录用于保存项目生成过程中产生的目标文件

output

output目录用于保存由编译器主程序main运行编译指定代码所产生的llvm IR及利用llc生成的汇编文件和使用clang生成的可执行文件

主要包括：

output
- 编译器编译获得可执行文件
output.ll
- llvm IR代码
output.o
- llc生成目标代码

include

include目录保存接口文件，主要用于外部调用和内部实现分离，main.cpp主要调用include下头文件。

相关代码中可按需添加额外的外部接口相关函数，此处未作拓展

src

src保存编译器前端即词法分析器，语法分析器，ir生成器等相关源码。

并定义子Makefile完成相关目标代码生成工作，如下

CXXFLAGS = -c -std=c++17
OBJDIR = ../build/obj

all:
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(LEXER)/$(LEXER).cpp -o $(OBJDIR)/$(LEXER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(PARSER)/$(PARSER).cpp -o $(OBJDIR)/$(PARSER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(IRGENERATOR)/$(IRGENERATOR).cpp -o $(OBJDIR)/$(IRGENERATOR).o
    cd ..

lexertest:
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(LEXER)/$(LEXER).cpp -o $(OBJDIR)/$(LEXER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(LEXER)/$(LEXER)_test.cpp -o $(OBJDIR)/$(LEXER)_test.o
    cd ..

parsertest:
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(LEXER)/$(LEXER).cpp -o $(OBJDIR)/$(LEXER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(PARSER)/$(PARSER).cpp -o $(OBJDIR)/$(PARSER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(IRGENERATOR)/$(IRGENERATOR).cpp -o $(OBJDIR)/$(IRGENERATOR).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(PARSER)/$(PARSER)_test.cpp -o $(OBJDIR)/$(PARSER)_test.o
    cd ..

irgeneratortest:
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(LEXER)/$(LEXER).cpp -o $(OBJDIR)/$(LEXER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(PARSER)/$(PARSER).cpp -o $(OBJDIR)/$(PARSER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(IRGENERATOR)/$(IRGENERATOR).cpp -o $(OBJDIR)/$(IRGENERATOR).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(IRGENERATOR)/$(IRGENERATOR)_test.cpp -o $(OBJDIR)/$(IRGENERATOR)_test.o
    cd ..

继承自相关父Makefile变量定义如下：

export CXX = g++
export LDFLAGS = $(shell llvm-config --ldflags)
export INCLUDES = $(shell llvm-config --cxxflags)
export LIBS = $(shell llvm-config --libs)
export LEXER = lexer
export PARSER = parser
export SEMANTICANALYZER = semanticanalyzer
export IRGENERATOR = irgenerator

lexer

lexer目录保存词法分析实现和测试相关代码

parser

parser目录保存语法分析实现和测试相关代码

AST

AST目录保存抽象语法树(AST)的节点定义

semanticanalyzer

semanticanalyzer目录可用于编写语义信息检查相关代码，实际在需要保存语义信息时，该任务可同步在作语法分析时在一遍中完成，因此实际的语义处理相关分布在AST和parser目录下相关代码中。

此处未添加相关AST检查代码，因此为空，但仍保留可用于按需拓展

irgenerator

irgenerator目录保存IR生成实现和测试相关代码，部分定义需要结合AST下代码。

test_codes

test_codes目录保存用于编译器测试的代码，简单介绍如下：

basic.txt
- 随意编写了基础代码，测试基本内容和for，++，--等
procedure_simcal.txt
- 编写了过程调用测试代码，验证过程调用正确性，含scan语句
procedure_withoutscan.txt
- 同样为过程调用测试代码，不包含scan语句
array.txt
- 编写了基本的数组测试代码
array2.txt
- 编写更复杂的数组测试代码

simplecompiler

simplecompiler目录保存web界面实现相关代码，该目录下组织结构与实际web应用结构相同，可实际放置在服务器中运行。

index.php和compiler.php分别为简单的编译器界面和后端调用编译器处理实现

tmpcode
- 保存临时写入的llvm IR文件
build
- 保存临时生成的中间文件，意义类似build目录

运行方式

编译

项目采用make命令编译，包含根目录下父Makefile和src下子Makefile定义编译规则，其中父Makefile负责根据不同任务调用子Makefile规则编译并对目标代码作链接完成可执行文件生成；子Makefile则根据父Makefile调用指令完成所需目标代码生成工作。

父Makefile定义如下：

export CXX = g++
CXXFLAGS = -std=c++17

BINDIR = ./build/bin
OBJDIR = ./build/obj
OUTPUTDIR = ./build/output

TARGET = main

SRCS = $(notdir $(filter-out %_test.cpp,  $(wildcard ./src/**/*.cpp) main.cpp))
OBJS = $(SRCS:%.cpp=%.o)

export LDFLAGS = $(shell llvm-config --ldflags)
export INCLUDES = $(shell llvm-config --cxxflags)
export LIBS = $(shell llvm-config --libs)

export LEXER = lexer
export PARSER = parser
export SEMANTICANALYZER = semanticanalyzer
export IRGENERATOR = irgenerator

default: $(TARGET)

complier: $(TARGET)

all: $(TARGET) lexertest parsertest irgeneratortest

$(TARGET): OBJS
    $(CXX) $(CXXFLAGS) $(LDFLAGS) $(LIBS) $(addprefix $(OBJDIR)/,$(OBJS))  -o $(BINDIR)/$@ -lncurses -w

OBJS:
    cd src && make all
    $(CXX) -c $(CXXFLAGS) $(INCLUDES) main.cpp -o $(OBJDIR)/main.o

lexertest:
    cd src && make lexertest
    $(CXX) $(CXXFLAGS) $(LDFLAGS) $(LIBS) $(OBJDIR)/$(LEXER)*.o -o $(BINDIR)/$(LEXER)_test -lncurses -w

parsertest:
    cd src && make parsertest
    $(CXX) $(CXXFLAGS) $(LDFLAGS) $(LIBS) $(OBJDIR)/$(LEXER).o $(OBJDIR)/$(PARSER)*.o $(OBJDIR)/$(IRGENERATOR).o -o $(BINDIR)/$(PARSER)_test -lncurses -w

irgeneratortest:
    cd src && make irgeneratortest
    $(CXX) $(CXXFLAGS) $(LDFLAGS) $(LIBS) $(OBJDIR)/$(LEXER).o $(OBJDIR)/$(PARSER).o $(OBJDIR)/$(IRGENERATOR)*.o -o $(BINDIR)/$(IRGENERATOR)_test -lncurses -w

clean:
    rm -rf $(OBJDIR)/*
    rm -rf $(BINDIR)/*
    rm -rf $(OUTPUTDIR)/*

子Makefile定义如下：

CXXFLAGS = -c -std=c++17
OBJDIR = ../build/obj

all:
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(LEXER)/$(LEXER).cpp -o $(OBJDIR)/$(LEXER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(PARSER)/$(PARSER).cpp -o $(OBJDIR)/$(PARSER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(IRGENERATOR)/$(IRGENERATOR).cpp -o $(OBJDIR)/$(IRGENERATOR).o
    cd ..

lexertest:
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(LEXER)/$(LEXER).cpp -o $(OBJDIR)/$(LEXER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(LEXER)/$(LEXER)_test.cpp -o $(OBJDIR)/$(LEXER)_test.o
    cd ..

parsertest:
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(LEXER)/$(LEXER).cpp -o $(OBJDIR)/$(LEXER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(PARSER)/$(PARSER).cpp -o $(OBJDIR)/$(PARSER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(IRGENERATOR)/$(IRGENERATOR).cpp -o $(OBJDIR)/$(IRGENERATOR).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(PARSER)/$(PARSER)_test.cpp -o $(OBJDIR)/$(PARSER)_test.o
    cd ..

irgeneratortest:
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(LEXER)/$(LEXER).cpp -o $(OBJDIR)/$(LEXER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(PARSER)/$(PARSER).cpp -o $(OBJDIR)/$(PARSER).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(IRGENERATOR)/$(IRGENERATOR).cpp -o $(OBJDIR)/$(IRGENERATOR).o
    $(CXX) $(CXXFLAGS) $(INCLUDES) ./$(IRGENERATOR)/$(IRGENERATOR)_test.cpp -o $(OBJDIR)/$(IRGENERATOR)_test.o
    cd ..

注意关于llvm编译涉及头文件、库文件路径等参数可以通过llvm-config工具获取，可以使用llvm-config --help获取使用帮助
- llvm-config --libs
- 获取所需库文件
- llvm-config --cxxflags
- 获取gcc编译所需参数
- llvm-config --ldflags
- 获取链接所需参数

相关Makefile部分编写规则可参考“Makefile编写”：https://williamshen.cn/wordpress/?p=54

基本的编译命令如下，分别产生不同任务编译不同程序：

make
- 编译编译器主程序
make all
- 编译包括编译器主程序，各部分测试程序等在内的所有程序。效果等同于“make ， make lexertest，make parsertest，make irgeneratortest”
make lexertest
- 编译词法分析器测试程序
make parsertest
- 编译语法分析器测试程序
make irgeneratortest
- 编译IR生成器测试程序
make clean
- 清理所有编译过程产生文件

运行

直接运行

可以直接运行./build/bin目录下相关可执行文件，可使用llc，clang等工具编译llvm IR生成可执行文件。

例如在根目录下可通过以下方式在shell(/terminal)中运行：./build/bin/main "文件名"

e.g. ./build/bin/main "./test_codes/procedure_simcal.txt"

为方便运行编写了shell脚本，简化操作

脚本运行

start.sh内容如下：

clear
./build/bin/main "./test_codes/procedure_simcal.txt"
echo Executing program ...
echo u may type in input then ... if there isn\'t, nvm ...
./build/output/output
echo Program execution finished. Bye.

start.sh首先清空屏显内容，后续运行编译器编译指定输入文件中代码，

随后通过echo内容回显提示信息，然后自动执行编译器主程序生成的对应输入代码的可执行文件

test.sh内容如下：

clear
./build/bin/irgenerator_test "./test_codes/array.txt"

test.sh内容较为简单，清空屏显内容，执行对应可执行文件

在终端通过sh xxx.sh命令即可运行对应脚本

Web界面运行

项目以提供Web界面编译程序，相关界面在./simplecompiler目录下，对于本机可使用http://localhost:8080/simplecompiler/index.php 或 http://127.0.0.1:8080/simplecompiler/index.php访问，

界面大致如下：

Figure 2 编译器Web界面

此时在左侧框体内输入代码，点击左下角"Compile"按键，输出信息将在右侧显示，LLVM IR界面将显示编译获得的llvm IR代码，输出界面将显示编译对应代码并执行可执行文件后得到的输出

本机访问时请注意配置好代理如nginx，apache，端口号可能根据不同配置而不同，详情可参考“Web简单说明”一节
Web界面仅为简单交互，不支持实时交互，每次新提交输入都会覆盖之前信息，因此不支持scan语句，其他语句均能正常支持
同时提供一公网访问方式，http://simplecompiler.williamshen.cn（注意是http非https，该域名未配置对应证书，暂无法通过https协议访问）
- 公网服务器上主程序暂时无法运行，考虑为llvm动态链接的问题，缺少必要组件运行。因服务器配置问题，无法配置llvm环境，需考虑其他解决方案如交叉编译等，但该问题超出编译原理本身暂且搁置，但观察界面已足够

运行说明

关于运行，有以下几点需要强调

关于Web界面暂不支持scan语句，有需要的可尝试自行修改相关文件
公网Web界面暂时因可执行文件原因，无法正常工作，当然也可尝试观察回显内容，输出应当类似返回类似“可执行文件main无法运行”的反馈，关于可执行文件问题见3。若需要访问Web界面的仍建议配置好本地环境在本机上访问
关于可执行文件，仍建议是完整配置好完整环境运行，否则可能无法运行
1. 实验环境为X86架构MacOS，完整配置llvm，可执行文件运行正常
2. 另一环境为X86架构Alibaba Cloud Linux(基于CentOS)，未配置llvm(yum似乎能够配置llvm，但至少CentOS目前源下的llvm并不是完整的项目，并且版本并不是较新)，可执行文件无法运行

关于可执行文件，可以尝试运行可执行文件并使用file，uname命令查看相关属性，操作系统为Alibaba Cloud Linux(基于CentOS)，结果如下：

Figure 3 CentOS下未配置llvm可执行文件执行和属性查看

至少在CentOS下file命令可以查看可执行文件flags(MacOS下无flags)，含动态链接flag，因此推测是动态链接导致的问题

代码说明

本小节将对相关代码作简要介绍，并不会针对具体实现做十分细节的解释，而是对部分设计、函数、定义做简单介绍。llvm相关详细介绍有更专业的文档和书籍相较于该文档更值得阅读，同时《LLVM编译器实战教程》一书作者也提及“代码即文档”的说法，在缺乏文档支持的条件下，代码可以帮助理解，确实是一个比较好的想法，因此读者可以阅读相关代码甚至实际运行获得更好的理解。

因为精力的有限，暂无法对全部内容作讲解还请理解，同时对代码质量和可读性问题，尚处于学习阶段还请见谅。

同时说明部分主要针对主程序，相关测试程序读者感兴趣的可以自行阅读和尝试

Lexer

词法分析器部分较为简单，

以下为定义的token，并使用map从string映射到TokenType用于保留字的搜索

//lexer.hpp
enum TokenType
    {
        eoi,
        unknown,
        ident,
        number,
        plus,
        minus,
        times,
        slash,
        plusplus,
        minusminus,
        eql,
        neq,
        lss,
        leq,
        gtr,
        geq,
        lparen,
        rparen,
        lbrace,
        rbrace,
        lbracket,
        rbracket,
        comma,
        semicolon,
        becomes,
        mainsym,
        ifsym,
        thensym,
        elsesym,
        endsym,
        whilesym,
        forsym,
        scansym,
        printsym,
        proceduresym,
        returnsym
    };

   static const std::unordered_map<std::string, TokenType> reservedKeywords;

//...

//lexer.cpp

//...

const std::unordered_map<std::string, Token::TokenType> Token::reservedKeywords = {
    {"main", mainsym},
    {"if", ifsym},
    {"then", thensym},
    {"else", elsesym},
    {"end", endsym},
    {"while", whilesym},
    {"for", forsym},
    {"scan", scansym},
    {"print", printsym},
    {"procedure",proceduresym},
    {"return",returnsym}
};

定义Token类用于保存token的类型和字符

class Token{

//...

private:

    TokenType type;
    llvm::StringRef text;
};

识别出token后通过InitializeToken初始化

void Lexer::InitializeToken(Token& token, const char* tokenEnd, Token::TokenType type)
{
    token.SetType(type);
    token.SetText(llvm::StringRef(bufferPtr, tokenEnd - bufferPtr));

    bufferPtr = tokenEnd;
}

对于token的识别则可以采用简单的有限状态自动机识别，识别流程如下：

Figure 4 词法分析状态转换图

Parser & Semantic Analyzer

语法分析部分并未严格按照文法规则采用递归下降的方式实现，而是根据实际需要作了简化。

一般的语法分析部分采用递归下降的方式与运算符优先的方式相结合来实现，但给定文法定义将项、因子等分离弱化了对运算符优先级的判断，因此以递归下降的方式为主。

因此涉及相关语法分析函数如下：

std::unique_ptr<Program> ParseProgram();
std::unique_ptr<Stmtlist> ParseStmtlist();
std::unique_ptr<Stmt> ParseStmt();
std::unique_ptr<Stmt> ParseAssignstmt();
std::unique_ptr<Stmt> ParseIfstmt();
std::unique_ptr<Stmt> ParseWhilestmt();
std::unique_ptr<Stmt> ParseScanstmt();
std::unique_ptr<Stmt> ParsePrintstmt();
std::unique_ptr<Stmt> ParseForstmt();
std::unique_ptr<Boolexpr> ParseBoolexpr();
std::unique_ptr<Expr> ParseExpr();
std::unique_ptr<Term> ParseTerm();
std::unique_ptr<Factor> ParseFactor();
std::unique_ptr<Ident> ParseIdent();
std::unique_ptr<Number> ParseNumber();

其它一些主要的辅助函数如：

void Advance()
{
  lexer.GetNext(token);
}

bool Consume(Token::TokenType tokenType)
{
  if (IsNextTokenOfType(tokenType))
  {
    return true;
  }
  llvm::outs()<<(std::string)token.GetText()<<" ";
  if (token.IsOneOf(Token::lbrace,Token::semicolon))
  {
    llvm::outs()<<"\n   ";
  }
  Advance();
  return false;
}

Advance函数在处理完一个token后获取下一个token；

Consume函数使用Advance函数，相当于确定一个非终结符获取下一个token

生成llvm IR需要使用到抽象语法树AST，在做语法分析的同时完成语义信息的保存

AST各类节点定义如下：（codegen用于IR代码生成，此处可暂忽略）

class Program
{
    std::vector<std::string> procedurename;
    std::vector<std::vector<std::unique_ptr<Ident>>>    procedureargs;
    std::vector<std::unique_ptr<Stmtlist>> procedurestmt;
    std::vector<std::unique_ptr<Ident>> procedurereturn;
    std::unique_ptr<Stmtlist> S;
public:
    Program(std::unique_ptr<Stmtlist> S,std::vector<std::string> procedurename, std::vector<std::vector<std::unique_ptr<Ident>>> procedureargs,std::vector<std::unique_ptr<Stmtlist>> procedurestmt,std::vector<std::unique_ptr<Ident>> procedurereturn): 
    S(std::move(S)),procedurename(procedurename),procedureargs(std::move(procedureargs)),procedurestmt(std::move(procedurestmt)),procedurereturn(std::move(procedurereturn)) {}
    llvm::Value *codegen();
};

属性	描述
prodecurename	向量存储可能的多个过程名
procedureargs	向量存储每个过程的参数列表
procedurestmt	向量存储每个过程的具体语句
procedurereturn	向量存储每个过程的返回值
S	存储语句序列

class Stmtlist
{
    std::vector<std::unique_ptr<Stmt>> S;   //Vector to Store Stmts
public:
    Stmtlist(std::vector<std::unique_ptr<Stmt>> S): S(std::move(S)) {}
    llvm::Value *codegen();
};

属性	描述
S	使用向量存储多条语句

/*  Base Class for All Stmts   */
class Stmt
{
public:
    virtual ~Stmt() = default;
    virtual llvm::Value *codegen() = 0;
};

Stmt为各类语句基类，由此派生出多个类定义不同类型语句

class Assignstmt : public Stmt 
{
    std::unique_ptr<Ident> LHS; //Left Value
    std::unique_ptr<Expr> RHS;  //Right Value
public:
    Assignstmt(std::unique_ptr<Ident> LHS, std::unique_ptr<Expr> RHS): LHS(std::move(LHS)), RHS(std::move(RHS)) {}
    llvm::Value *codegen() override;
};

属性	描述
LHS	赋值语句左值
RHS	赋值语句右值

class Ifstmt : public Stmt 
{
    std::unique_ptr<Boolexpr> Bools;    //Condition
    std::unique_ptr<Stmtlist> Stmtlistthens;    //Then Stmtlists
    std::unique_ptr<Stmtlist> Stmtlistelses;    //Else Stmtlists, Note It can Be Nullptr when There is No Else
public:
    Ifstmt(std::unique_ptr<Boolexpr> Bools, std::unique_ptr<Stmtlist> Stmtlistthens, std::unique_ptr<Stmtlist> Stmtlistelses=nullptr):
    Bools(std::move(Bools)), Stmtlistthens(std::move(Stmtlistthens)), Stmtlistelses(std::move(Stmtlistelses)) {}
    llvm::Value *codegen() override;
};

属性	描述
Bools	if语句条件
Stmtlistthens	then语句
Stmtlistelses	else语句

class Whilestmt : public Stmt
{
    std::unique_ptr<Boolexpr> Bools;    //Condition
    std::unique_ptr<Stmtlist> Stmtlists;    //Body
public:
    Whilestmt(std::unique_ptr<Boolexpr> Bools, std::unique_ptr<Stmtlist> Stmtlist): Bools(std::move(Bools)),Stmtlists(std::move(Stmtlist)) {}
    llvm::Value *codegen() override;
};

属性	描述
Bools	while语句循环条件
Stmtlists	循环体

class Scanstmt : public Stmt
{
    std::vector<std::unique_ptr<Ident>> S;  //Args List
public:
    Scanstmt(std::vector<std::unique_ptr<Ident>> S): S(std::move(S)) {}
    llvm::Value *codegen() override;
};

属性	描述
S	scan参数列表

class Printstmt : public Stmt
{
    std::vector<std::unique_ptr<Expr>> S;   //Args List
public:
    Printstmt(std::vector<std::unique_ptr<Expr>> S): S(std::move(S)) {}
    llvm::Value *codegen() override;
};

属性	描述
S	print参数列表

class Forstmt : public Stmt
{
    std::unique_ptr<Stmt> Assigns;  //Assign before For Stmt
    std::unique_ptr<Boolexpr> Bools;    //Condition
    std::unique_ptr<Expr> Exprs;    //Expr after each For
    std::unique_ptr<Stmtlist> Stmtlists;    //Body
public:
    Forstmt(std::unique_ptr<Stmt> Assigns, std::unique_ptr<Boolexpr> Bools, std::unique_ptr<Expr> Exprs, std::unique_ptr<Stmtlist> Stmtlists):
    Assigns(std::move(Assigns)),Bools(std::move(Bools)),Exprs(std::move(Exprs)),Stmtlists(std::move(Stmtlists)) {}
   llvm::Value *codegen() override;
};

属性	描述
Assigns	for语句初始赋值语句
Bools	for循环条件
Exprs	for语句循环后执行表达式
Stmtlists	for循环体

class Expr
{
    bool uminus;
    std::vector<std::unique_ptr<Term>> terms;   //Vector to Store terms
    std::vector<std::string> ssigns;    //Vector to Store Operator
public:
    Expr(bool uminus, std::vector<std::unique_ptr<Term>> terms, std::vector<std::string> ssigns):
        uminus(uminus), terms(std::move(terms)), ssigns(std::move(ssigns)) {}
    llvm::Value *codegen();
};

属性	描述
uminus	是否有符号，1为是0为否
terms	向量存储每个项
ssigns	向量存储每个项之间的+或-操作

class Boolexpr
{
    std::string Op;
    std::unique_ptr<Expr> LHS,RHS;
public:
    Boolexpr(const std::string& Op, std::unique_ptr<Expr> LHS, std::unique_ptr<Expr> RHS): Op(Op),LHS(std::move(LHS)),RHS(std::move(RHS)) {}
    llvm::Value *codegen();
};

属性	描述
Op	布尔表达式操作赋
LHS	左侧操作符数
RHS	右侧操作数

class Term
{
    std::vector<std::string> Op;    //Store Operator
    std::vector<std::unique_ptr<Factor>> S; //Vector to Store Factors
public:
    Term(std::vector<std::string> Op, std::vector<std::unique_ptr<Factor>> S) : Op(std::move(Op)), S(std::move(S)) {}
    llvm::Value *codegen();
};

属性	描述
Op	向量存储各因子间的操作符
S	向量存储各因子

class Factor
{
    bool incre; //Whether There is Increment OR Decrease, Even Though We only Use incre to Represent, 1 for Yes & 0 for No
    bool prefix;    //Whether the Operator is Prefix or Suffix, 1 for Prefix & 0 for Suffix
    std::string Op;
    std::unique_ptr<Ident> Name_ident;  //Store Idents
    std::unique_ptr<Expr> Name_expr;    //Store Exprs, Valid if isexpr is 1
    bool isexpr;    //Whether Is Expr or not, 1 for Yes & 0 for No
    bool isnumber;  //Whether Is Num or not, 1 for Yes & 0 for No
    std::unique_ptr<Number> Num;    //Store Num, Valid if isnumber is 1
    bool isprocedure;
    std::string procedurename;
    std::vector<std::unique_ptr<Ident>> procedureargs;
public:
    Factor(bool incre,bool prefix,const std::string& Op,std::unique_ptr<Ident> Name_ident,std::unique_ptr<Expr> Name_expr,bool isexpr,bool isnumber, std::unique_ptr<Number> Num,bool isprocedure,
    std::string procedurename,
    std::vector<std::unique_ptr<Ident>> procedureargs)
    : incre(incre),prefix(prefix),Op(Op),Name_ident(std::move(Name_ident)),Name_expr(std::move(Name_expr)),isexpr(isexpr),isnumber(isnumber),Num(std::move(Num)),isprocedure(isprocedure),procedurename(procedurename),procedureargs(std::move(procedureargs)) {}
    llvm::Value *codegen();
};

属性	描述
incre	是否有自增自减运算符，1为是
prefix	自增自减运算符是否是前缀或后缀，1为前缀，0为后缀
Op	因子间运算符
Name_ident	存储标识符
Name_expr	存储表达式，isexpr为1时有效
isexpr	是否为表达式，1为是
isnumber	是否为常数，1为是
Num	存储常数，isnumber为1时有效
isprocedure	是否是过程调用，1为是
procedurename	调用过程名
procedureargs	过程调用的参数列表

class Ident
{
    std::string Name;   //Name of the Ident
    bool isarray;
    std::vector<int> idx;
public:
    Ident(const std::string& Name,bool isarray,std::vector<int> idx) : Name(Name),isarray(isarray),idx(idx) {}
    llvm::Value *codegen();
    std::string getName()
    {
        return Name;
    }
    bool getArray()
    {
        return isarray;
    }
    std::vector<int> getidx()
    {
        return idx;
    }

};

属性	描述
Name	标识符名
isarray	是否是数组
idx	此次访问数组时下标集，isarray为1时有效

class Number
{
    int Val;    //Value of the Number
public:
    Number(int Val) : Val(Val) {}
    llvm::Value *codegen();
    int getVal()
    {
        return Val;
    }
};

Number保存数值即可

属性	描述
Val	保存具体数值

此外还定义集合结构存储过程名，以在语义信息保存时及时保存过程名

static std::set<std::string> procedureNames;

语法分析和语义分析同步进行，使用递归下降的方式分析语法，并且同步地将创建一抽象语法树将语义信息保存，以ParseProgram为例做简单介绍

std::unique_ptr<Program> Parser::ParseProgram()
{
    std::vector<std::string> procedurename;
    std::vector<std::vector<std::unique_ptr<Ident>>>    procedureargs;
    std::vector<std::unique_ptr<Stmtlist>> procedurestmt;
    std::vector<std::unique_ptr<Ident>> procedurereturn;
    debugtextP("Parsing Program");
    while (token.Is(Token::proceduresym))
    {
        Consume(Token::proceduresym);
        if (!token.Is(Token::ident))
        {
            LogErrorP("Expecting ident");
            return nullptr;
        }
        else
        {   
            procedureNames.insert((std::string)(token.GetText()));
            procedurename.push_back((std::string)(token.GetText()));
            Consume(Token::ident);
            if (Consume(Token::lparen))
            {
                LogErrorP("Expecting \"(\"");
                return nullptr;
            }
            else
            {
                std::vector<std::unique_ptr<Ident>> arglist;
                if (!token.Is(Token::ident))
                {
                    LogErrorP("Expecting ident");
                    return nullptr;
                }
                arglist.push_back(std::move(ParseIdent()));
                while (token.Is(Token::comma))
                {
                    Consume(Token::comma);
                    arglist.push_back(std::move(ParseIdent()));
                }
                procedureargs.push_back(std::move(arglist));
                if (Consume(Token::rparen))
                {
                    LogErrorP("Expecting \")\"");
                    return nullptr;
                }
                else
                {
                    if (Consume(Token::lbrace))
                    {
                        LogErrorP("Expecting \"{\"");
                        return nullptr;
                    }
                    else
                    {
                        procedurestmt.push_back(std::move(ParseStmtlist()));
                        if (Consume(Token::returnsym))
                        {
                            LogErrorP("Expecting \"return\"");
                            return nullptr;
                        }
                        else
                        {
                            if (!token.Is(Token::ident))
                            {
                                LogErrorP("Expecting ident");
                                return nullptr;
                            }
                            else
                            {
                                procedurereturn.push_back(std::move(ParseIdent()));
                                if (Consume(Token::semicolon))
                                {
                                    LogErrorP("Expecting \";\"");
                                    return nullptr;
                                }
                                else
                                {
                                    if (Consume(Token::rbrace))
                                    {
                                        LogErrorP("Expecting \"}\"");
                                        return nullptr;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    if (Consume(Token::mainsym))
    {
        LogErrorP("Expecting \"main\"");
        return nullptr;
    }
    else
    {
        if (Consume(Token::lbrace))
        {
            LogErrorP("Expecting \"{\"");
            return nullptr;
        }
        else
        {
            debugtextP("Going to parse Stmtlist");
            auto Result = std::make_unique<Program>(ParseStmtlist(),procedurename,std::move(procedureargs),std::move(procedurestmt),std::move(procedurereturn));
            if (!Result)
            {
                LogErrorP("Wrong Stmt");
                return nullptr;
            }

            if (Consume(Token::rbrace))
            {
                LogErrorP("Expecting \"}\"");
                return nullptr;
            }
            else
            {
                if (!token.Is(Token::eoi))
                {
                    LogErrorP("Program end wrongly!");
                }
                else
                {
                    return Result;
                }
            }

        }
    }
}

主要步骤如下：

初始化
- 定义了多个存储解析结果的向量，包括过程名称、过程参数、过程语句列表和过程返回值。
解析过程 (procedure)
- 使用 while 循环解析所有的过程 (procedure)。
- 每个过程以关键字 proceduresym 开始：
  - 检查并Consume proceduresym 标志。
  - 确认过程名是标识符并Consume它。
  - 解析过程参数列表：
  - Consume左括号 (。
  - 解析标识符参数，使用逗号分隔。
  - Consume右括号 )。
  - 解析过程的主体（语句列表）：
  - Consume左大括号 {。
  - 调用 ParseStmtlist 解析语句列表。
  - 解析返回值：
  - Consume return 关键字。
  - 确认并Consume返回值标识符。
  - Consume分号 ;。
  - Consume右大括号 } 结束过程。
解析主程序 (main)
- 检查并Consume mainsym 关键字。
- Consume左大括号 {。
- 调用 ParseStmtlis 解析主程序的语句列表。
- 构造并返回 Program 对象，包含主程序和所有过程的信息。
- Consume右大括号 } 结束主程序。
- 确认程序结束标志 eoi

成功解析后，返回包含程序信息的 std::unique_ptr\。

后续其他语法分析和语义分析同理，此处不再展开

IR Generator

IR生成需要使用以下结构:

std::map<std::string,llvm::Value*> NamedValues;  //Table to Store address for each Ident
std::map<std::string,std::vector<int>> arrayinfo;

NamedValues作用为符号表保存标识符对应内存中的地址
arrayinfo作用为保存每次初始化数组时保存数组开辟空间大小即各维度最大值

以下结构用于llvm生成IR

std::unique_ptr<LLVMContext> TheContext = std::make_unique<LLVMContext>();
std::unique_ptr<Module> TheModule = std::make_unique<Module>("simple complier", *TheContext);
std::unique_ptr<IRBuilder<>> Builder = std::make_unique<IRBuilder<>>(*TheContext);

FunctionType *funcType = FunctionType::get(Builder->getVoidTy(), false);
Function *mainFunc = Function::Create(funcType, GlobalValue::ExternalLinkage, "main", *TheModule);
BasicBlock *entryBlock = BasicBlock::Create(*TheContext, "entry", mainFunc);

TheContext用于存储与 LLVM 相关的全局数据。它包含了诸如类型表、常量表等数据结构。提供了上下文环境供其他llvm对象使用
TheModule表示一个独立的编译单元，它包含了所有的全局变量、函数及其他数据结构。用于组织和管理生成的 IR 代码，最终的目标是将该模块编译成目标代码或字节码
Builder则用于生成IR代码
funcType用于定义和声明函数，使得编译器知晓函数的调用约定和参数信息
mainFunc用于表示程序的主函数或其他函数，包含函数体和基本块等结构
entryBlock用作生成IR代码时的入口基本块

IR生成器的思路大致采取值的传递来完成，仅在最底层，即处理标识符代码时可能开辟空间存储变量，并返回变量在内存中地址。而在上层中获取到地址后均可以按照编写代码load值或store值，以及对load的值作运算。

Value* Ident::codegen() 
{
    debugtextIR("Generating Ident code");
    std::string name = getName();

    if (NamedValues.find(name) != NamedValues.end()) 
    {
        debugtextIR("Found in table");
        return NamedValues[name];
    } 
    else if (isarray)
    {
        std::vector<int> arysize;
        debugtextIR("Going to alloca space for array");
        int arraysize = 1;
        for (size_t i = 0; i < idx.size() ; i++)
        {
            arraysize *= (idx[i]+1);
            arysize.push_back((idx[i]+1));
        }
        ArrayType* array_type = ArrayType::get(Type::getInt32Ty(TheModule->getContext()), arraysize);
        Value* array = Builder->CreateAlloca(array_type);
        arrayinfo[name] = arysize;

        NamedValues[name] = array;

        return array;
    }
    else 
    {
        debugtextIR("Going to alloca space for ident");
        //If the ident hasn't exist, save in the table
        llvm::AllocaInst *V = Builder->CreateAlloca(Builder->getInt32Ty(), nullptr, name);
        NamedValues[name] = V;

        return V;
    }
}

更近一步查看ident的代码生成函数，

当在符号表中能够查找到变量，则返回对应地址，否则
- 若是数组，则计算需要的空间，开辟空间，保存信息并将起始地址存入符号表中
- 若是普通变量，则开辟空间，将地址存入符号表中

同样以Program为例对代码生成部分作简要介绍

Value* Program::codegen()
{
    if (!procedurename.empty())
    {
        debugtextIR("Generating procedure code if there are");
        for (size_t i = 0; i < procedurename.size(); ++i)
        {
            std::vector<Type*> parameters(procedureargs[i].size(), Builder->getInt32Ty());
            FunctionType* functionType = FunctionType::get(Builder->getInt32Ty(), parameters, false);
            Function* function = Function::Create(functionType, GlobalValue::ExternalLinkage, procedurename[i], *TheModule);
            BasicBlock* block = BasicBlock::Create(Builder->getContext(), "entry", function);
            Builder->SetInsertPoint(block);
            //TheModule->print(outs(),nullptr);
            int idx = 0;
            for (auto &Arg : function->args())
            {
                Arg.setName((std::string)procedureargs[i][idx++]->getName());
            }
            NamedValues.clear();
            for (auto &Arg : function->args())
            {

                AllocaInst* alloca = Builder->CreateAlloca(Type::getInt32Ty(*TheContext), nullptr, Arg.getName() + ".addr");

                Builder->CreateStore(&Arg, alloca);

                NamedValues[std::string(Arg.getName())] = alloca;

            }
            debugtextIR("Going to create return for procedure");
            procedurestmt[i]->codegen();
            Value *retvalue = Builder->CreateLoad(llvm::Type::getInt32Ty(TheModule->getContext()),NamedValues[procedurereturn[i]->getName()]);
            Builder->CreateRet(retvalue);
            debugtextIR("Going to verify procedure");
            verifyFunction(*function);
        }
    }

    Builder->SetInsertPoint(entryBlock);
    auto result = S->codegen();
    Builder->CreateRetVoid();
    verifyFunction(*mainFunc);

    return result;
}

Program中由codegen实现了程序中过程和主函数的代码生成逻辑。以下是对该函数的详细说明：

检查和生成过程代码
- 判断是否有过程：
```
if (!procedurename.empty())
```
  如果 procedurename 不为空，则说明程序中存在过程，进入代码生成部分。
- 循环生成每个过程的代码：
```
for (size_t i = 0; i < procedurename.size(); ++i)
```
  对每个过程进行以下处理：
  - 定义过程参数类型：
```
std::vector parameters(procedureargs[i].size(), Builder->getInt32Ty());
```
  为过程的每个参数设置类型为int32。
  - 创建过程的函数类型和函数对象：
```
FunctionType* functionType = FunctionType::get(Builder->getInt32Ty(), parameters, false);
Function* function = Function::Create(functionType, GlobalValue::ExternalLinkage, procedurename[i], *TheModule);
```
  创建一个函数类型 functionType（返回类型为 int32），并使用该类型创建一个新的函数 function，将其添加到模块中。
  - 创建函数的入口基本块并设置插入点：
```
BasicBlock* block = BasicBlock::Create(Builder->getContext(), "entry", function);
Builder->SetInsertPoint(block);
```
  为函数创建一个名为 "entry" 的基本块，并将 IR 生成器的插入点设置到该基本块。
  - 设置函数参数的名称并创建 Alloca 指令：
```
for (auto &Arg : function->args())
{
   Arg.setName((std::string)procedureargs[i][idx++]->getName());
}
```
  遍历函数的参数并设置每个参数的名称。然后，为每个参数通过 alloca 指令，将参数存储到栈上，并将其存储到符号表中：
```
for (auto &Arg : function->args())
{
   AllocaInst* alloca = Builder->CreateAlloca(Type::getInt32Ty(*TheContext), nullptr, Arg.getName() + ".addr");
   Builder->CreateStore(&Arg, alloca);
   NamedValues[std::string(Arg.getName())] = alloca;
}
```
  - 生成过程体的代码：
```
procedurestmt[i]->codegen();
```
  调用过程体的codegen方法生成过程体的 IR 代码。
  - 生成返回指令：
```
Value *retvalue = Builder->CreateLoad(llvm::Type::getInt32Ty(TheModule->getContext()),NamedValues[procedurereturn[i]->getName()]);
Builder->CreateRet(retvalue);
```
  从 NamedValues 中获取地址，load值以后生成返回指令。
  - 验证生成的函数：
```
verifyFunction(*function);
```
  调用 verifyFunction 验证生成的函数是否有效。
生成主函数代码
- 设置主函数的插入点：
```
Builder->SetInsertPoint(entryBlock);
```
- 生成主函数体的代码：
```
auto result = S->codegen();
```
- 生成主函数的返回指令：
```
Builder->CreateRetVoid();
```
- 验证主函数：
```
verifyFunction(*mainFunc);
```
返回生成的结果
- 返回主函数体代码生成的结果：
```
return result;
```

其余代码生成函数同理，都按照通常来说的IR代码格式根据语义生成对应的IR来完成对应任务。

有需要进一步了解llvm IR的可以阅读相关文档，此处篇幅有限不再作进一步介绍和展开。

Main

main.cpp为编译器主程序，统筹了词法分析，语法分析，语义分析和IR生成工作。并调用llc，clang工具来完成相应的后端工作以完整的完成一个编译器工作

main.cpp内容如下：

#include "llvm/Support/CommandLine.h"
#include "llvm/Support/InitLLVM.h"
#include "llvm/Support/raw_ostream.h"
#include <iostream>
#include <fstream>
#include <sstream>
#include "include/lexer_interface.hpp"
#include "include/parser_interface.hpp"
#include "include/irgenerator_interface.hpp"

int main(int argc, const char** argv)
{
    llvm::InitLLVM llvmInitializer(argc, argv);
    //llvm::cl::opt<std::string> input(llvm::cl::Positional, llvm::cl::desc("<input expression>"), llvm::cl::init(""));
    llvm::cl::opt<std::string> inputFilename(llvm::cl::Positional, llvm::cl::desc("<input file>"), llvm::cl::init(""));
    llvm::cl::ParseCommandLineOptions(argc, argv, "A simple complier\n");

    /*  Processing Input File  into string stream */
    if (inputFilename.empty()) 
    {
        llvm::errs() << "No input file specified\n";
        return 1;
    }

    std::ifstream inputFile(inputFilename);
    if (!inputFile.is_open()) 
    {
        llvm::errs() << "Could not open input file: " << inputFilename << "\n";
        return 1;
    }

    std::stringstream buffer;
    buffer << inputFile.rdbuf();
    std::string input = buffer.str();
    llvm::outs() << "Input: \"" << input << "\"\n\n";

    Lexer lexer(input); //Lexer
    Parser parser(lexer);   //Parser & Semantic Analyzer
    std::unique_ptr<Program>  tree = parser.Parse();    //AST Construction
    if (!tree || parser.HasError())
    {
        llvm::errs() << "Syntax errors occured\n";
        return 1;
    }

    tree->codegen();    //Code Generation

    std::error_code EC;
    llvm::raw_fd_ostream dest("./build/output/output.ll", EC);

    if (EC)
    {
        llvm::errs() << "Could not open file: " << EC.message();
        return 1;
    }

    TheModule->print(dest, nullptr);    //Writing IR Code into File output.ll
    dest.flush();

    //Our Target is output(.exe), which will be Placed under the ./build/ouput Dir
    std::string Command = "llc -filetype=obj ./build/output/output.ll -o ./build/output/output.o && export SDKROOT=$(xcrun --sdk macosx --show-sdk-path) && clang ./build/output/output.o -o ./build/output/output";
    int result = system(Command.c_str());   //Using llvm tool(i.e. llc) to Complete Backend Tasks(e.g. Optimize, Generating obj File etc.)
    if (!result)
    {
        llvm::outs()<<"\nCompile and generate obj file successd!\n";
    }
    else
    {
        llvm::outs()<<"\nCompile and generate obj file failed!\n";
    }

    return result;

}

利用llvm提供的参数处理工具读入文件流后写入字符串流，以后开始正式准备编译器工作：

lexer读入字符串流，分割为token
parser读入分割后token，进行语法分析并生成AST
从AST开始代码生成工作，生成IR代码，并将代码写入"./build/output/output.ll"文件中

调用llc和clang完成由llvm IR到可执行文件的编译工作，写为“./build/output/output”程序

llc -filetype=obj ./build/output/output.ll -o ./build/output/output.o && export SDKROOT=$(xcrun --sdk macosx --show-sdk-path) && clang ./build/output/output.o -o ./build/output/output

至此已完成前端和后端的统筹，形成了最终的编译器

Web简单说明

Web界面并不在编译原理范畴内，因此此小节将对Web界面做简要介绍并不会深入，主要包含Nginx的简单配置和Web简单说明。

另外作者对php并不是十分熟悉，有需要的读者可以去阅读专门文档或书籍

Nginx配置

Nginx配置可参考如下：

server {
    listen       8080;

    server_name localhost;  #可替换为实际域名

    #charset koi8-r;
    #access_log  /var/log/nginx/host.access.log  main;

    location  / {
        proxy_pass /your/website/Root/index.php; #替换为实际根录如http://127.0.0.1/simplecompiler/index.php
    }

    location ~ \.php$ {
        #将该路径替换为您的网站根目录。
        root           /your/website/Root/;
        #Nginx通过unix套接字与PHP-FPM建立联系，该配置与/etc/php-fpm.d/www.conf文件内的listen配置一致。
        fastcgi_pass   unix:/run/php-fpm/www.sock;
        fastcgi_index  homepage.php;
        #将/scripts$fastcgi_script_name修改为$document_root$fastcgi_script_name。
        fastcgi_param  SCRIPT_FILENAME  $document_root$fastcgi_script_name;
        #Nginx调用fastcgi接口处理PHP请求。
        include        fastcgi_params;
    }
}

本机访问时请注意端口，若公网访问按实际添加80和443端口与配置中，并确保放行80(http)和443(https)端口
请正确配置php，并添加在代理规则中正确配置php-fpm，否则获取php文件时，无法传递给后端php解释器解析，不能正确的到页面，此时尝试访问页面提示应该是“file not found”
- 关于Nginx部分报错，可参考“Nginx报错汇总”：https://williamshen.cn/wordpress/?p=87

Web说明

index.php为简单界面设计，compile.php中完成了生成临时代码，运行可执行文件，调用llc，clang等编译的逻辑，其内容如下：

<?php
if ($_SERVER['REQUEST_METHOD'] === 'POST') 
{
    $code = $_POST['code'];

    //filter input
    if (empty($code)) {
        header("Location: index.php?output=" . urlencode("Error: No code provided."));
        exit();
    }

    //create tmp dir in case if not
    $tempDir = './tmpcode/';
    if (!is_dir($tempDir)) {
        mkdir($tempDir, 0777, true);
    }

    $tempCodeFile = $tempDir . 'tmp_code.txt';
    file_put_contents($tempCodeFile, $code);

    //compile the code
    $mainCommand = escapeshellcmd("./main \"$tempCodeFile\"");
    $mainOutput = shell_exec($mainCommand . ' 2>&1');
    if ($mainOutput) {
        echo "<pre>Main Command Output:\n$mainOutput</pre>";
    }

    //read llvm ir
    $llFile = './build/output/output.ll';
    $llContent = '';
    if (file_exists($llFile)) {
        $llContent = file_get_contents($llFile);
    }

    $llcCommand = escapeshellcmd("llc -filetype=obj $llFile -o ./build/output/output.o");
    $llcOutput = shell_exec($llcCommand . ' 2>&1');
    if ($llcOutput) {
        echo "<pre>LLC Command Output:\n$llcOutput</pre>";
    }

    putenv('PATH=' . getenv('PATH') . ':/usr/bin');
    $clangCommand = escapeshellcmd("clang ./build/output/output.o -o ./build/output/output");
    $clangOutput = shell_exec($clangCommand . ' 2>&1');
    if ($clangOutput) {
        echo "<pre>Clang Command Output:\n$clangOutput</pre>";
    }

    //check compile result
    if (!file_exists('./build/output/output')) {
        // 编译失败
        $output = "Compilation failed:\n$mainOutput\n$llcOutput\n$clangOutput";
    } else {
        //run target programe
        $runCommand = escapeshellcmd('./build/output/output');
        $runOutput = shell_exec($runCommand . ' 2>&1');
        $output = $runOutput;

        //clean tmp file
        unlink('./build/output/output.ll');
        unlink('./build/output/output.o');
        unlink('./build/output/output');
    }

    //clean tmp code
    unlink($tempCodeFile);

    //redirect to main page and send back content
    header("Location: index.php?output=" . urlencode($output) . "&llcontent=" . urlencode($llContent));
    exit();
}
?>

当传递的是POST方法时，将首先将临时代码写入指定目录./tmpcode中；后续调用main编译生成IR代码；最后调用llc和clang生成目标代码和可执行文件并清理产生中间文件，将shell结果保存并回显

测试

basic.txt

basic.txt内容如下：

main
{
    a = 5;
    scan(b);
    for (c=0;c<a;c++)
    {
        if (b >= c)
        then
        {
            b = b + 1;
        }
        else
        {
            print(b);
        }
        end;
    };
    d = 10;
    while (a != d)
        {
            a = a + 1;
            b = b + a;
            print(b) ;
        };
    print(a,b);
}

为随意编写的一段测试for，while，scan，print，++等基础功能的程序

当输入为10时，得到结果如下：（第一行10为输入）

Figure 5 basic执行结果

终端中完整输出内容如下:

Input: "main
{
    a = 5;
    scan(b);
    for (c=0;c<a;c++)
    {
        if (b >= c)
        then
        {
            b = b + 1;
        }
        else
        {
            print(b);
        }
        end;
    };
    d = 10;
    while (a != d)
        {
            a = a + 1;
            b = b + a;
            print(b) ;
        };
    print(a,b);
}"

main { 
   a = 5 ; 
   scan ( b ) ; 
   for ( c = 0 ; 
   c < a ; 
   c ++ ) { 
   if ( b >= c ) then { 
   b = b + 1 ; 
   } else { 
   print ( b ) ; 
   } end ; 
   } ; 
   d = 10 ; 
   while ( a != d ) { 
   a = a + 1 ; 
   b = b + a ; 
   print ( b ) ; 
   } ; 
   print ( a , b ) ; 
   } 

Compile and generate obj file successd!
Executing program ...
u may type in input then ... if there isn't, nvm ...
10
21
28
36
45
55
10
55
Program execution finished. Bye.

尝试手动计算，计算过程如下：

次序	a	b	c	d	备注
1	5	10	-	-	scan(b)，输入10
2	5	10	0	-	for初始化c，进入for循环
3	5	11	1	-	第一次for循环结束
4	5	12	2	-
5	5	13	3	-
6	5	14	4	-
7	5	15	5	-	不满足for循环条件，退出for循环
8	5	15	5	10	初始化d，准备进入while循环
9	6	21	5	10	print(b)，输出21
10	7	28	5	10	print(b)，输出28
11	8	36	5	10	print(b)，输出36
12	9	45	5	10	print(b)，输出45
13	10	55	5	10	print(b)，输出55
14	10	55	5	10	print(a,b)，输出10，55

可以验证逻辑正确，基础功能测试通过

procedure_simcal.txt

procedure_simcal.txt内容如下：

procedure multiply(ma,mb)
{
    mr = ma * mb;
    return mr;
}

procedure add(aa,ab)
{
    ar = aa + ab;
    return ar;
}

main
{
    scan(a,b,c,d);
    rl = add(a,b);
    rr = add(c,d);
    r = multiply(rl,rr);
    ro = (a+b)*(c+d);
    print(r);
    print(ro);
}

程序逻辑为读取a，b，c，d，并分别通过直接运算和调用过程的方式计算(a+b)*(c+d)，并打印结果，如下：

Figure 6 procedure_simcal执行结果

当输入3，4，5，6时，将计算(3+4)*(5+6)，结果为77，结果正确。

procedure_withoutscan.txt

procedure_withoutscan.txt内容如下：

procedure multiply(ma,mb)
{
    mr = ma * mb;
    return mr;
}

procedure add(aa,ab)
{
    ar = aa + ab;
    return ar;
}

main
{
    a=4;
    b=2;
    c=3;
    d=6;
    rl = add(a,b);
    rr = add(c,d);
    r = multiply(rl,rr);
    ro = (a+b)*(c+d);
    print(r);
    print(ro);
}

该测试适用直接赋值代替scan语句计算(4+2)*(3+6)，结果如下：

Figure 7 procedure_withoutscan执行结果

使用Web界面测试结果如下：

Figure 8 procedure_withoutscanWeb界面执行结果(1)

Figure 9 procedure_withoutscanWeb界面执行结果(2)

Figure 10 procedure_withoutscanWeb界面执行结果(3)

可以验证结果正确性，同时在Web界面中也可以查看生成的llvm IR代码

array.txt

basic.txt内容如下：

main{
    a[3][3][3] = 10;
    a[3][3][2] = 5;
    b = a[3][3][3];
    c = a[3][3][2];
    print(b,c);
    a[3][3][0] = b + c;
    d = a[3][3][0];
    print(d);
}

该测试用于测试简单的数组操作和使用，结果如下：

Figure 11 array执行结果

容易验证其正确性

array2.txt

basic.txt内容如下：

main{
    a[3][3][3] = 10;
    b[3][3][2] = 5;
    c = a[3][3][3];
    d = b[3][3][2];
    print(c,d);
    a[3][3][0] = a[3][3][3] + ++b[3][3][2];
    a[3][3][1] = a[3][3][3] + b[3][3][2];
    e = a[3][3][0];
    f = a[3][3][0] + 5;
    g = a[3][3][1]--;
    h = a[3][3][1];
    print(e,f,g,h);
}

该测试对数组进行了更复杂的操作，例如增加++，--，并区分了前后缀之分，运行结果如下：

Figure 12 array2执行结果

可以验证其正确性，例如g，h分别为a[3][3][1]后缀--运算前后结果分别为16，15，逻辑正确。

Web界面编译的到IR和输出如下：

Figure 13 array2Web界面执行结果(1)

Figure 14 array2Web界面执行结果

Figure 15 array2Web界面执行结果

可以验证Web界面运行的正确性

局限性

对于可执行文件在不同平台上运行的兼容性测试仍有待加强，目前仅在正确配置llvm的环境下验证似乎可以运行可执行文件，在其他平台上，似乎会因为缺少llvm组件导致无法执行可执行文件，包括公网服务器上部署Web应用也因同样问题无法正确运行，考虑过静态链接解决但过程并不理想，未来可能考虑类似交叉编译等手段
对于AST和IR生成上，因初次上手，并不具有一个全面的认识，并且对于llvm的应用尚处于起步阶段，在相关设计方面并不是十分完善，导致了代码质量和可读性的降低，未来可能考虑深入相关理论夯实基础
在文法规则方面，在给定规则上进行改动，但似乎并不是一个好的设计，原本在语法分析方面，通常采用递归下降和运算符优先相结合方式设计，但在给定规则中将项，因子等可以拆开故对运算符优先级予以弱化；同时最开始的设计暂未考虑多种类型的定义，在当前设计下，继续拓展类型，需要同时普及到函数参数，数组类型，返回类型等，在现有代码上更改将不可避免的令代码质量和可读性大大降低。未来可能考虑一个更加完善的文法定义和规则以便更清晰合理的完成相关设计

代码链接

https://gitee.com/WilliamSamShen/complier-concepts/tree/master/Project/v_llvm

注：

目前Project下存在v_1和v_llvm两版本，v_1起始为基于PL/0设计，但仅建立了项目结构未有实现，后续建立基于llvm的版本
v_1版本可能考虑删除，不再可访问

参考文章

My First Language Frontend with LLVM Tutorial https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index.html
编译器 https://blog.csdn.net/zhanglin_wu/category_11835780.html
IR API(五)——使用LLVM提供的C接口和IRBuilder来生成LLVM IR常用方法总结 https://blog.csdn.net/qq_42570601/article/details/108059403
《LLVM编译器实战教程》Bruno Cardoso Lopes & Rafael Auler 著

基于llvm的编译器设计与实现_课程Project

基于llvm的编译器设计与实现

简述

文法定义

原始定义

拓展后定义

文法规则

SELECT集计算

\

\

\

\

\

\

\

\

\

\

\

\

\

\

\

\

\

\

LLVM概述

环境说明及配置

环境说明

环境配置

项目结构说明

build

bin

obj

output

include

src

lexer

parser

AST

semanticanalyzer

irgenerator

test_codes

simplecompiler

运行方式

编译

运行

直接运行

脚本运行

Web界面运行

运行说明

代码说明

Lexer

Parser & Semantic Analyzer

IR Generator

Main

Web简单说明

Nginx配置

Web说明

测试

basic.txt

procedure_simcal.txt

procedure_withoutscan.txt

array.txt

array2.txt

局限性

代码链接

参考文章