小序 Abstract

余闻，古有大贤能者，怀大神通，俱玄妙幽深之大法也。若晓习之，可使铁石通得人言。尝想往之，然不知其所在，故不得往，不知其名号，故不得访。
或问曰：何不问旁人矣？呜呼哀哉！今人者，多搬来搬去之徒，目光短浅之辈，生性愚钝，盲然自大，罔识大法，问之空徒劳矣！

某日夜中，余寐，飘飘乎神往，往而遇一神山，高可百余丈，烟尘浩渺，草木葱茏，沿小径行，有二老翁奕者，余不敢近前，只敢远观，静听其言。其所言者，余不懂也，但有一名号，余虽未曾闻之，但觉甚是熟识，曰：
编译原理 Fundamentals Of Compiling
及余醒时，方知已半月有余矣。此为一年前之事也。此名号者，余不懂也，故走访山川，欲寻门路，寻而未得，怅怅而归。虽未曾得，但得知此乃上古大贤能之神通也。

归，余将路途见闻，及些许访得，一一书录，籍以留念，不作他用。
言辞愚钝，文笔拙劣，十分惭愧，甚至九分。

【甲辰年丁丑月癸未日，云水书】

正规表达式 Regular Expression

正规表达式
正规表达式者谓如 张三 & 李四 | 王五 * 之类，运算者三：
一曰 '与' ，书曰 & ，谓前后之相随；
二曰 '或' ，书曰 | ，谓并肩于左右；
三曰 '星' ，又云 '闭包' ，书曰 * ，谓有一有二再三再四者；
另有括号为用，法同四则运算。

其形
形当何如？形当如树！缘何如树？缘有括号！
若无括号，当若列表；因有括号，故而如树；括号者，内者先外者后；树者，子树先而兄弟后；
故曰：见得括号，始一子树；别得括号，终一子树。

字符集 Alphabet (番外)

古时洋文，其字二十有六，其数方十，其号不过卌，总不俞百，可一一书而录之，今字数如沙尘，万不可矣！故需分段，书录两端，记以名号，用时依旧。
或问曰：古之字者名号一一不同，今若两段有交有错，则名号二矣，当若何如？
噫，善哉！两段之间，关系者三：
一者，不交，则左段之右左于右段之左，名号如故；
二者，包合，则左段之右右于右段之右，依左左，右左，右右，左右分三，名号另立，以或合；
三者，交错，非一非二者乃是交错，依左左，右左，左右，右右分三，名号另立，以或合；

有限自动机 Finite Automata

古之大贤能者有云，有一神山，凡人不可见者；山中有限自动机神兽大王：
初其首，终其尾，左膀状态一众，右臂字符一众；身中怀图，唤作轮转方图，行则来处，行列间谓去处，其列者，长幼异焉；
确定性有限自动机， DFA 者，长者也，大王也；独首九尾，列者实字，实字者，谓不可空也，善断句成词；
非确定性有限自动机， NFA 者，幼者也，幼王也；九首九尾，列者可三，谓字空式也，善识正规表达式。

非确定性有限自动机 Nondeterministic Finite Automata

识正规表达式
幼王识正规表达式者，每见一式，生一首尾，做一初终，如不展开，列者式也。
或问曰：展开者何如？
答曰：展开者，列者字也，初其初，终其终，依法展开：
若 初 --张与李-> 终 者，新取一状态，展为 初 --张-> 新 --李-> 终 ；
若 初 --张或李-> 终 者，展为 初 --张-> 终 与 初 --李-> 终 ；
若 初 --张闭包-> 终 者，新取一状态，展为 初 --空-> 新 --空-> 终 与 新 --张-> 新 ；
括号何如？树已析之。若张李等有子树，则依样展开如故。

NFA 到 DFA

幼王长成大王者，当先展开，确定化即成大王；而后可简化，亦可不简。

秘法
古有见过幼王长成之神人，言其图中秘之秘法，有二：
一曰 Esplion 闭包 ，予一状态众，得其等价之众，形如 'Ps' 之 '扩大选取' ；诀曰：广搜其得着大空而有去处者众，兼其去处，尽皆书录。
二曰 Ia ，予一状态众做初，予一字，得其去处之众；诀曰：遍查其初，尽录其去，以 Esplion 闭包 广之方成。

确定化 Determines
确定化者，形如广搜，取旧首众，以 Esplion 闭包 广之，合做新首；逐字广搜 Ia 之众，合做新状态，尽皆书录，照做新图；中含旧尾者合做新尾，名号一如旧尾，如是长成矣。
或问曰：若二旧尾合做一新尾者，名号何如？
答曰：二尾合一者，则正规表达式中有形异而实同者也。如此这般者，尚未可知也。

简化 Simplify
简化者，合众状态为一，一分二，二分三，至无可分者也。
一分二者，谓合尾为一，余者为二也；
二分三者，逐字尽计所去，似若 Ia ，然略有异焉，异者，此需辨无去处者另计；若去处二则分之，分至无可分则止。

确定性有限自动机 Deterministic Finite Automata

大王断句者，予一状态，置于首，取字逐食，状态依图中来去而轮转，食一字而一去，至尾则得一词；复置之于首，如上这般，直至无所食。
或问曰：若有一般，有来无去，何如？
答曰：当噎死矣，速速抢救！

语法 Grammar

古之大贤能者又云，又有沧海，凡人不可见者，海中有上下文无关文法神龙大王，属性文法圣龙大王，递归下降与移进归约两大护法大王，及一众拥护大王等若干，善读文章者也。

产生式 Production

产生式者，谓如 张三 -> 李四众 | 王五众 之类，分则若 张三 -> 李四众 与 张三 -> 王五众 ；
意曰化生彼此，分一则众，合众则一；其形如树，一者其根，始也，统领也，众者支叶，从者也，终也；可分化者，谓非终结符也，不分化者，谓终结符也。
故张三者，或化李众，或化王众；李者，可合而化张，王者一也；

Esplion
Esplion 者，曰大空，若 张 -> Esplion 者，言张可化无，无可生张者也，曰直接之大空。
若有 张 -> 李 与 李 -> Esplion 者，则张化李，李化无，故张亦可化无也，曰间接之大空。

上下文无关文法 Context-free Grammar

若产生式一众，总计其始终一众，选上极无上者一，曰大统领，开始符号也，此曰上下文无关文法大王。
如 张 -> 李赵 | 王 与 李 -> 赵王 合者，则谓张李曰非终结者众，谓赵王曰终结者众，大统领者张也。

属性文法 Attribute Grammar

上下文无关文法大王者，断得其文，不解其意；若与张李等，抒予其意，指身为对象，置属性以承传，则其意得解，故此号曰属性文法大王。
所谓属性者，若张三有某物，则曰此物为张三属性；源自父及兄弟者，曰继承属性，其自上而下者也，如其不然，曰综合属性，其自下而上者也。

L 属性文法
L 属性文法者，属性文法之一也，合有综合属性与继承属性者也。
其貌何如？曰：属性者，先予而后用，后不用先不予者，则必为 L 属性文法大王也。
如 张 -> (张这般这般，李赵承之) 李赵 (李赵张这般这般，张承之) 者，统领者张，从者李赵；李赵承者，继承属性也，张之承者，综合属性也。

S 属性文法
或问曰：若无继承属性者何如？
答曰：此 S 属性文法大王也，形如 张 -> 李赵 (李赵张这般这般，张承之) 。

递归下降

递归下降，玄妙之至也。其自上而下矣。
如若一树者，起于父，兄先，始于自身，继之子孙，终以自身，弟后，止于父，及其之上，一也。
若论先后，则左者先而右者后；左者，来也，上先而下后；右者，去也，下先而上后。若指自身，分之则三：先者，父及兄也，后者，弟及父也，中间者，子孙也。
或问曰：其形何如？
答曰：吾未曾得见其形，但闻大贤能者云，上古有圣兽，曰函数执行大王也，亦自上而下，自左而右也。方其行时，分而作三：先者于先，始者启一栈帧，继而行，终者去一栈帧，后者于后。若论其形，何所似也！

LL1 文法

LL1 文法大王，乃上下文无关文法之化生也，若以上下文无关文法为初，解左递归而成，可简化亦可不简。

左递归 Left Recursion
左递归者，若 张 -> 张李 者，左领以张，右初亦张；若张为初，即生张李，初者亦张，又可化生，无穷无尽，不可终也，此谓左递归也；凡人可见者曰直接左递归，凡人难察者，曰间接左递归。
古有大贤能者，访得解左递归秘法：

直接左递归
直接左递归者，若 张 -> 张李 | 王 者，籍以小张，变左递归为右递归，解之为 张 -> 王小张 与 小张 -> 李小张 | 大空 即成。诀曰：各付小张于后；集左递归者众，弃其首，并一大空，予小张统领乃解。

秘法 (番外)
此法不知从何来矣，但作参考：
若 张三 -> 张四李 | 王 者，又曰 三 -> 四 (...李) | 王 者，
易四以王，得 三 -> 王 (李...李) ，
立 小张 -> 李...李 ，又曰 小张 -> 李小张 | 大空 者，易之即成矣。

间接左递归
间接左递归者，曰：集众统领序列之，逐个验视，明察从者其首，有统领在先者，分之为众，而后解其直接左递归即解。
或问曰：解间接左递归大法者，其形何如？
答曰：古有内联函数大王者，其形甚相似也。

简化 Simplify
简化者，以大统领为初，广搜其不达者，尽皆拂去即可。

LL1 分析法

LL1 分析器
LL1 分析器大王者，由 LL1 文法大王化生而来，善读文章。
其化生者，初其初，终其终，怀 LL1 文法，造预测分析图方得；欲造预测分析图者，需先造三图；
三图者，夫递归下降之分三，弃其先，照中后做 First 与 Follow 二图，合做 Select 图，继以造预测分析图方得。

秘法
古有见造 First 与 Follow 者，言其中秘之秘法，曰乾坤轮转大法：
今之乾坤为旧，另做乾坤为新，照旧化得，曰一轮转；若新旧有异，则化新为旧，化旧成新，依样这般。

First
First 者，一也，谓某统领所分化者众，取其领头之非终结众也；分三者之中间者也；若子孙之长者。
曰：终结者指身为一也，非终结者遍访子孙，集其长者非终结者众也。
若 张 -> 李赵等 者，张之一者，李之一也，弃其大空；若李可化无，则赵之一亦也，亦弃大空；若赵亦可化无，其后亦亦；若李赵等皆可化无，则并一大空。

Follow
Follow 者，随也，谓于某统领之后者众，取其领头之非终结众也；分三者之后者也；若弟侄之长者，无弟侄则代以表兄弟等。
大之大统领者，长之长者，上极无上，无父无兄弟者，其随者，大之大空也。
若有 张 -> 李赵 者，李之随者，赵之一也，弃其大空；若赵可化无，则张之随亦也。

Select
Select 者，选也，谓某统领所分化者与其之后者众，取其领头之非终结众也；分三之中后二般也；集其子孙众，一也，若可化无者，另集弟侄众，随也。
若有 张 -> 李赵 者，张之选者，李赵一也，若李赵可化无，兼张之随也。
若此中众，一一不同，则藉以此，统领为行，终结者列，行列间式，一格一式，照做预测分析表，号曰 M ，弃三图，方成 LL1 分析器大王。
或问曰：若二式一格者，何如？
答曰：如此则哀哉，大王将夭矣。

识文章
夫大王始读文章，将一栈，置大之大空于底，置大统领者开始符号于其上，同置大之大空于文章尾；读时，逐取词，照栈其上：
若终结词与大之大空者，若与栈上同，得之，移去栈上；如其不然，大王当背过气去。
若非终结词者，栈上为行，词以列，照预测分析表取，若取得式，则移去栈上，反序入栈众从者，亦得之；若不得式，大王亦背过气去。

自顶向下语法制导翻译 STD

自顶向下者，需解左递归。解左递归者，需 S 属性文法矣。其法，亦 LL1 大王之解左递归大法者也，唯一异者，属性承传也：
其承传者，代承代转也。若 张 -> 李赵 者，则承之者张；及大法付小张于后者，则小张代承，籍以转予。

直接左递归
若 张三 -> 张四李 (四李这般这般，三承之) 及 张 -> 王 (王那般那般，张承之) 者，
需解之为 张 -> 王 (王那般那般，小张代承) 小张 (小张转予张) 与 小张三 -> 李 (三李这般这般，四代承之) 小张四 (四转予三) 及 小张 -> 大空 (承己) 即可。
或曰： 得解者好似 L 属性文法也。
曰：善哉，正是如此矣。

间接左递归
间接左递归者照旧，若 张 -> 李 (这般这般) 赵 (那般那般) 先而 王 -> 张 (如此如此) 刘 后，则化后为 王 -> 李 (这般这般) 赵 (那般那般) (如此如此) 刘 即可。

用者
其用时，与 LL1 分析器大王者同，唯一异者，属性承传也：
其承传者，如函数运行大王也。故曰：
将一栈，凡非终结者入栈，分身为二，各号起止，起者出栈，启一栈帧，止者出栈，弃一栈帧；
余者：终结者出栈，配得属性；这般那般出栈，即照做也。