1. Scala：解析器组合子与DSL
为了和MySQL数据库进行交互，我们的唯一方式是使用SQL语句，它是一个强大的，声明式编程的领域特定语言DSL。尝到"甜头"的我们希望自己能够创造一门微型语言，让它能够对某类文件的解析，或者在特殊业务中发挥作用，提高开发效率。
比如，"创造"一个诸如wheresthinaTuple的句式快速完成对元组的检索。不过，这需要解析器（以及词法解析器）来将这些语句转换成本地程序能够理解的数据结构。对于学习者而言，这很难，因为你至少要成为精通《编译原理》的专家。即便你是专家，这仍然是非常麻烦的一件事情。
Scala提供了解析器组合子库，允许我们在Scala体系下实现一个内部的，简单的领域特定语言，或者称之内部DSL。Scala有一些特性可方便的支持内部DSL开发：函数柯里化、隐式转换、允许使用符号名称（这一点非常重要）、允许使用``空格替代对象调用的.符号等。
在阅读本章之前，你可能需要对上下文无关文法(context-freegrammar)有一个基本的认识。在简单介绍Scala解析器组合子的用法之后，我们会尝试制作一个支持将JSON格式的字符串转换为Scala对应数据结构的解析器。
绪论：上下文无关文法产生式一个产生式是由一个条件和动作组成的指令，即条件—活动规则：condition-action。它通常用于表述具有因果关系的知识，其基本形式为P→Q，或者称为ifPthenQ。
终结符终结符是一个形式语言的基本符号，它不能被分解（或者替换成）更小的符号。比如给定两个产生式构成的文法：
S::=aSbS::=ba
其中，::=可以使用->符号代替，它代表着“相当于”的含义。在这个文法中，S可以被替换为aSb，或者是ba，但是a和b却不能够再替代成其它的符号。因此，a和b是终结符。
非终结符非终结符，即表示可以被替代的符号。显然，在上述的文法中，S是一个非终结符。在同一个文法下，一个符号不是终结符就是非终结符。
形式文法形式文法，可以简单的理解为它是一个这样的元组：(N,Σ,P,S)。其中：
N代表着非终结符号集合。
Σ代表着终结符号集合。
P代表着一系列产生式规则。
S代表一个起始符号，其中S属于N。
从直观的形式来看，形式文法是一系列产生式规约而形成的准则，或称是一系列"公式"，或者是"模板"。继续拿刚才的例子来说：
S::=aSbS::=ba
显然，这个文法描述了这样的字符串集合：ba，abab，aababb等。因为我们可以从初始符号S出发，通过类似这样的推导过程：S->aSb->aaSbb得到上述的字符串。
形式文法的类型分为四种：无限制文法，上下文文法，上下文无关文法和正规文法。其中，划线部分为本章重点提及的文法。
Sent::=SVOS::={人|天}V::={吃|下}O::={雨|肉}
其中，S代表主语，V代表谓语，O代表宾语。根据刚才的判断方式，这是一个上下文无关文法，因为所有产生式左边只有一个单独的非终结符。
从初始符号Sent出发，我们可以得到以下的句子：
显然，由于上下文无关，在造句时完全不用考虑"动宾搭配"等因素，我们可以任意选择搭配的S，V，O，而导致出现了一些语义错误的句子。在此时，我们必须要将此文法修正为上下文文法：
Sent::=SVOS::={人|天}人V::={人吃}天V::={天下}吃O::={吃肉}下O::={下雨}
其中，人V，天V都不再是单独的非终结符号。因为V和O的左侧都加了限定词，比如只有主语是"人"时，谓语才可以使用“吃“。
以"人吃饭"为例，其推导过程为：
在第三步中，V的上文是"人"，因此可以通过推导式第三条规则推出人吃O。
相关参考资料[CSDN]编译原理学习(二)
[CSDN]终结符和非终结符
算数表达式解析器在介绍完了上下文无关文法之后，我们试着用它表达出四则运算表达式，形如：(2*3)+4，4*2+1...它的文法如下：
在这里，{}内的内容是可重复的。内部的后备选项之间使用|符号分隔。另外，在本例中虽然没有提及，但是[]表示这是一个可选项。
注意，这个表达式(expr)都是由多个词(term)通过*或者/操作链接起来的。而词又是由多个因子(factor)通过*或者/操作链接起来的。而因子本身可以是一个浮点数(floatingPointNumber)或者是另一个被括号括起来的表达式。
"大因子"之间使用+/-操作，"小因子"之间使用*或/操作，这无形之间定义了操作符的运算优先级。
使用Scala工具实现你的表达式算术表达式的解析器包含在一个继承自JavaTokenParsers特质的类中，这里的Token含义为"符号"，因为该工具给出了诸多基础的解析器：标识符，字符串字面量，以及数字等解析器。在这个例子中，floatingPointNumber就是从该特质所提供的浮点数解析器。
给出文法的Scala工具实现：
importscala.util.parsing.combinator.{defexpr:Parser[Any]=term~rep("+"~term|"-"~term)defterm:Parser[Any]=factor~rep("*"~factor|"/"~factor)deffactor:Parser[Any]=floatingPointNumber|"("~expr~")"}下面是一些相关说明：
每个产生式在Scala中都是一个方法，它的返回值是Parser[Any]。我们稍后会介绍它的具体含义是什么。
在文法中，符号和expr,term,factor之间使用空格来表示顺序的组合关系，犹如"helloworld"这个句子中，各个单词使用空格来顺序衔接。而在Scala中，这个空格被替换成了~符号。为了使得代码和文法的视觉效果更加接近，在这里我们不在~的前后再加上空格。
|在Scala中是解析器组合子的其中一个。P|Q表示首先尝试使用P解析器进行解析，如果失败，则使用解析器Q。
在Scala表述的文法中，可重复项使用rep(...)来表示，可选项使用opt(...)来表示，它们都属于解析器组合子。
有关于~符号~是最常用的，用于顺序组合，的解析器组合子，比如P~Q代表着将P和Q的解析结果装入到另一个同样命名为~的模板类当中并返回。因此，假设P的解析结果是true，而Q的解析结果是?，那么P~Q将返回一个~("true","?")。注意，这是一个Parser特质的内部模板类。当打印它时，会得到(true~?)。
//theoperatorformerlyknownas+++,++,&,butnow,beholdthevenerable~//it'sshort,light(lookslikewhitespace),hasfewoverloadedmeaning(thankstotherecentchangefrom~tounary_~)//andweloveit!(ordowelike`,`better?)/**.**`p~q`succeedsif`p`succeedsand`q`succeedsontheinputleftoverby`p`.**@`p`(thisparser)*succeeds--evaluatedatmostonce,andonlywhennecessary.*@returna`Parser`that--onsuccess--returnsa`~`(likea`Pair`,*buteasiertopatternmatchon)thatcontainstheresultof`p`and*thatof`q`.`p`or`q`fails.*/@migration("Thecall-by-,.","2.9.0")def~[U](q:=>Parser[U]):Parser[~[T,U]]={lazyvalp=q//lazyargument(for(a<-this;b<-p)yieldnew~(a,b)).named("~")}这个for-yield语句最终会编译成this.flatMap(a=>p.map(b=>new~(a,b)))，最终返回一个~(a,b)。而~模板类的声明在此：
/**Awrapperoversequenceofmatches.**Given`p1:Parser[A]`and`p2:Parser[B]`,aparsercomposedwith*`p1~p2`willhavetype`Parser[~[A,B]]`.Thesuccessfulresult*.**Italsoenablespatternmatching,sosomethinglikethisispossible:**{{{*defconcat(p1:Parser[String],p2:Parser[String]):Parser[String]=*p1~p2^^{casea~b=>a+b}*}}}*/caseclass~[+a,+b](_1:a,_2:b){overridedeftoString="("+_1+"~"+_2+")"}这样做的好处是如果你使用了P~Q的解析器组合子，那么你后续可以使用形式一致的偏函数（或者理解为模式匹配）casep~q=>(...)提取出P和Q各自的解析结果p&q。这里涉及到另一个解析器组合子^^，我们在后续的文章中再提及它。
运行算数解析器让另一个程序入口继承Arith类，并且在主函数中调用parseAll方法，将expr作为初始符号和你指定的数学表达式字符串传递进去：
objectRunningTimeextendsArith{defmain(args:Array[String]):Unit={println(parseAll(expr,"(3+2)*2"))}}在解析完毕时，程序会输出[1.13]，它表示成功解析了从第1个字符到第13个字符之前的位置。实际上，这个字符串的长度为12，因此换句话说就是整个表达式都被成功解析。
在解析后，控制台还会紧跟parsed，并打印解析结果（而它的用处并不大，我们可以先不去关心）。如果该表达式解析失败了，则会打印failure:并输出错误原因。
正则表达式解析器floatingPointNumber是由JavaTokenParses提供的按照Java格式识别浮点数的解析器。不过，有时候我们希望能够解析一个类似于"0x11"，"0xAF"的数字，或者有识别特定文本格式的需求。此时，我们可以使用更通用的正则表达式解析器(RegularExpressionParser)。
下面的MyParser单例对象演示了如何制作一个能够解析电子邮箱格式的解析器：
{defidentEmail:Parser[String]="""w+([-+.]w+)*@w+([-.]w+)*.w+([-.]w+)*""".r}任何字符串后面加上.r方法，都将返回一个Parser解析器。同时字符串内容将视作正则表达式作为解析规则。下面试着在主函数中解析一个邮箱：
objectRunningTime{defmain(args:Array[String]):Unit={println(MyParser.parseAll(MyParser.identEmail,"[email protected]"))}}解析成功，则说明正则表达式正确，且解析器能够正常运行。该例中的MyParser继承自RegexParsers特质。Scala的解析器组合子是按照特质的继承关系来有序组织的，它们被包含在Scala.util.parsing.combinator当中。
Parser是最顶层的特质，它定义了最通用的解析框架。下一层是RegexParsers，它要求提供正则表达式来让解析器工作。更具体的特质是JavaTokenParsers，它实现了对Java定义的词或语言符号进行识别的解析器。
JSON解析器在本章节中，我们尝试着制作一个diy的JSON解析器。首先给出一个JSON文本，并尝试着分析它的结构：
{"addressbook":{"name":"John","address":{"street":"10Market","city":"SanFrancisco","zip":94244}},"phonenumbers":["408338-3238","408338-6892"]}在JSON中，每个对象(object)都使用一个{}包括起来，内部包含了由成员(member)组成的成员集合(members)，成员之间使用,符号分隔。每个成员又是由k:v格式的键值对。其中k规定为字符串类型，v是包含了各种数据结构的值(value)。值可以包含了另一个独立的对象obj，也可以包含一个数组arr。其中，数组内部是由值value包含的值的集合(values)。除此之外，值value还包含了字符串值，浮点数值，“null”，"true"，"false"。
下面给出解析JSON的上下文无关文法：
完整的解析器代码块也在下文给出：其中，成员集合(members)和值的集合(value)在这里使用了repsep方法替代。如repsep(member,",")表示这是一个由member组成的，并且由,符号分隔的序列。对于值的集合(values)同理。
{defvalue:Parser[Any]=obj|arr|stringLiteral|floatingPointNumber|"null"|"true"|"false"defmember:Parser[Any]=stringLiteral~":"~valuedefobj:Parser[Any]="{"~repsep(member,",")~"}"defarr:Parser[Any]="["~repsep(value,",")~"]"}由于JSON整体也可以看作是一个被{}包裹起来的，包含着一个大obj的value，因此，在主函数中我们选取value作为初始符号传递并解析：
{defmain(args:Array[String]):Unit={valjsonString:String="""|{|"addressbook":{|"name":"John",|"address":{|"street":"10Market",|"city":"SanFrancisco",|"zip":94244|}|},|"phonenumbers":[|"408338-3238",|"408338-6892"|]|}""".stripMarginprintln(parseAll(value,jsonString))}}这段代码会运行成功，并且控制台会打印：
[16.7]parsed:(({~List((("addressbook"~:)~(({~List((("name"~:)~"John"),(("address"~:)~(({~List((("street"~:)~"10Market"),(("city"~:)~"SanFrancisco"),(("zip"~:)~94244)))~}))))~})),(("phonenumbers"~:)~(([~List("408338-3238","408338-6892"))~]))))~})解析器输出转换虽然这个程序成功解析了JSON，但是我们解析后没有任何后续操作，因此现在打印的字符串都来自~模板类的toString方法。它输出的内容都晦涩难懂，看起来没有任何实际意义，无论是对于程序员还是Scala程序，直接理解这个输出结果都不是一件容易的事情，现在是时候对它进行一些处理了。如果能够把JSON对象映射为某个Scala内部的数据格式，那么处理数据的效率就高得多。更自然的表示方式应当是这样：
JSON依赖k-v键值对存储信息，因此我们很自然地想到使用Map作为主体的容器。
JSON内的数组使用Scala内部的List[Any]类型去表示。
JSON字符串使用Scala的String类型去表示。
JSON数值使用Scala的Double类型去表示。
ture,false,null转换成Scala对应的数据结构，而不是String。
我们这里要引入另外一个解析器组合子：^^。该符号衔接在另一个解析器的后面，并尝试对前者的输出结果进行转型操作。设P^^Q，而P的返回值是R，那么这步操作就可以理解为Q(R)（前提是P得到了正确的解析结果）。下面尝试着创造一个将字符串转换成浮点数的解析器：
//theoperatorformerlyknownas+++,++,&,butnow,beholdthevenerable~//it'sshort,light(lookslikewhitespace),hasfewoverloadedmeaning(thankstotherecentchangefrom~tounary_~)//andweloveit!(ordowelike`,`better?)/**.**`p~q`succeedsif`p`succeedsand`q`succeedsontheinputleftoverby`p`.**@`p`(thisparser)*succeeds--evaluatedatmostonce,andonlywhennecessary.*@returna`Parser`that--onsuccess--returnsa`~`(likea`Pair`,*buteasiertopatternmatchon)thatcontainstheresultof`p`and*thatof`q`.`p`or`q`fails.*/@migration("Thecall-by-,.","2.9.0")def~[U](q:=>Parser[U]):Parser[~[T,U]]={lazyvalp=q//lazyargument(for(a<-this;b<-p)yieldnew~(a,b)).named("~")}0现在使用它来升级我们JSON解析器的一部分，以ob
2. 编译原理 正则语言 二义文法 急~
这个没有一个好老师，自己咬文嚼字看懂是很累的
二义性文法
【定义】 若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。
二义性文法会引起歧义，应尽量避免之！
G(E)：E -> E+E | E*E | (E) | i
这两种展开
E E
E + E E * E
i E * E E + E i
i i i i
都可以表示i+i*i
所以;文法具有二义性。
3. 【编译原理】第二章：语言和文法
上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。
约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：
产生式
可以简写为：
如上例中，
可以简写为：
给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。
如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。
推导的反过程称为 归约 。
如果 ，则称 是 的一个 句型（sentential form ）。
由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：
例
文法
表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。
并、连接、幂、克林闭包、正闭包。
如上例表示为：
中必须包含一个 非终结符 。
产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。
上下文有关文法不包含空产生式（ ）。
产生式的一般形式：
即产生式左边都是非终结符。
右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。
例：（右线性文法）
以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：
正则文法能描述程序设计语言中的多数单词。
正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。
根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。
给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。
直接短语一定是某产生式的右部，但反之不一定。
如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。
二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。
4. 通过运行状态转换图识别正则文法的句子。
求解啊
5. 编译原理 不能被5整除的偶整数的正规文法和正规式
分析可知不能被5整除的偶整数的情况是所有两位以上不以0结尾的偶数(2,4,6,8)，不包括0。
因此，正则表达式为：([1-9][0-9]*[2,4,6,8])|[2,4,6,8]。正规文法为：
S-> A | [2,4,6,8]
A->B [2,4,6,8]
B->[1-9] C
C->[0-9] C | ε