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 | ε