20201207_#3#Syntactic (語法) Analysis - HackMD

Syntactic analysis = parsing = syntax analysis (語法分析); Concept of Parser ... Phrase Structure Grammar = Constituency Grammar (短語結構文法) ...        ownedthisnote   Published LinkedwithGitHub Like Bookmark Subscribe Edit --- title:20201207_#3#Syntactic(語法)Analysis tags:note,SyntacticAnalysis description: 1.每月的每一週，針對某一主題寫一份學習筆記 2.YYYYMMDD_#[1]#[學習筆記主題]=>記得填寫第幾份Proposal的學習筆記 --- #***20201207_#3#Syntactic(語法)Analysis*** *** >[TOC] > --- ##簡介Introduction ###Syntacticanalysis=parsing=syntaxanalysis(語法分析) *Thepurposeofthisphaseistodrawexactmeaning,oryoucansaydictionarymeaningfromthetext. *Syntaxanalysischecksthetextformeaningfulnesscomparingtotherulesofformalgrammar. >Ex:“hotice-cream”不合語意(semantic)=>語意分析 *Inthissense,**syntacticanalysismaybedefinedastheprocessofanalyzingthestringsofsymbolsinnaturallanguageconformingtotherulesofformalgrammar**. ###ConceptofParser  *任務：解析(parsing) *將輸入的text，檢查是否符合語法後，輸出結構化的表示形式(Ex:parsetree,abstractsyntaxtree...orotherhierarchicalstructure)。

>Itmaybedefinedasthesoftwarecomponentdesignedfortakinginputdata(text)andgivingstructuralrepresentationoftheinputaftercheckingforcorrectsyntaxasperformalgrammar. *Themainrolesoftheparse *Toreportanysyntaxerror. *Torecoverfromcommonlyoccurringerrorsothattheprocessingoftheremainderofprogramcanbecontinued. *Tocreateparsetree. *Tocreatesymboltable. *Toproduceintermediaterepresentations(IR,中間表示). --- ###TypesofParsing >Derivation(導出)dividesparsingintothefollowingstwotypes. 1.Top-downParsing  *theparserstartsconstructingtheparsetree**fromthestartsymbol**andthentriestotransformthestartsymboltotheinput. *常見的形式：使用遞迴(recursive)來處理輸入 >Themaindisadvantageof`recursivedescentparsing`isbacktracking(回溯). 2.Bottom-upParsing  *theparser**startswiththeinputsymbol**andtriestoconstructtheparsertreeuptothestartsymbol. --- ###ConceptofDerivation(導出) >Derivationisasetofproductionrules. >Duringparsing,weneedtodecidethenon-terminal(非終結符),whichistobereplacedalongwithdecidingtheproductionrulewiththehelpofwhichthenon-terminalwillbereplaced. *[TypesofDerivation](https://www.gatevidyalay.com/tag/leftmost-derivation-and-rightmost-derivation/) >Learnaboutthetwotypesofderivations,whichcanbeusedtodecidewhichnon-terminaltobereplacedwithproductionrule 1.Left-mostDerivation(最左導出) *輸入的句子形式將被掃描，並從左到右進行替換。

>Thesententialforminthiscaseiscalledtheleft-sententialform. 2.Right-mostDerivation(最右導出) *輸入的句子形式將被掃描，並從右到左進行替換。

>Thesententialforminthiscaseiscalledtheright-sententialform. *範例： *Considerthefollowinggrammar ``` S→aB|bA A→aS|bAA|a B→bS|aBB|b ``` *Letusconsiderastring`w=aaabbabbba`.Now,letusderivethestringw. 1.LeftmostDerivation >由左開始w=**aa**abbabbba :::info S→a**B** →aa**B**B    (UsingB→aBB) →aaa**B**BB   (UsingB→aBB) →aaab**B**B   (UsingB→bS→b) →aaabb**B**   (UsingB→bS→b) →aaabba**B**B  (UsingB→aBB) →aaabbab**B**  (UsingB→bS→b) →aaabbabb**S**  (UsingB→bS) →aaabbabbb**A** (UsingS→bA) →aaabbabbba (UsingA→a) :::  2.RightmostDerivation >由右開始w=aaabbabb**ba** :::info S→a**B** →aaB**B**    (UsingB→aBB) →aaBaB**B**   (UsingB→aBB) →aaBaBb**S**   (UsingB→bS) →aaBaBbb**A**  (UsingS→bA) →aaBa**B**bba  (UsingA→a) →aa**B**abbba  (UsingB→bS→b) →aaaB**B**abbba (UsingB→aBB) →aaa**B**babbba (UsingB→b) →aaabbabbba (UsingB→b) :::  --- ###ConceptofParseTree >Graphicaldepictionofaderivation. *Thestartsymbolofderivationservesastherootoftheparsetree. *在每個解析樹中，葉節點是終端，內部節點是非終端。

>Ineveryparsetree,theleafnodesareterminalsandinteriornodesarenon-terminals. --- ###ConceptofGrammar *Grammarisveryessentialandimportanttodescribethesyntacticstructureofwell-formedprograms. *Intheliterarysense,theydenotesyntacticalrulesforconversationinnaturallanguages. >LinguisticshaveattemptedtodefinegrammarssincetheinceptionofnaturallanguageslikeEnglish,Hindi,etc. :::info *AmathematicalmodelofgrammarwasgivenbyNoamChomskyin1956,whichiseffectiveforwritingcomputerlanguages. *Mathematically,agrammarGcanbeformallywrittenasa4-tuple(N,T,S,P)where ***N**or**$V_N$**=setofnon-terminalsymbols,i.e.,variables. ***T**or**∑**=setofterminalsymbols. ***S**=StartsymbolwhereS∈N ***P**denotestheProductionrulesforTerminalsaswellasNon-terminals.Ithastheformα→β,whereαandβarestringson$V_N$∪∑andleastonesymbolofαbelongsto$V_N$ ::: --- ###PhraseStructureGrammar=ConstituencyGrammar(短語結構文法) *Phrasestructuregrammar,introducedbyNoamChomsky,isbasedontheconstituencyrelation. *Constituencygrammarisopposite(相反)todependencygrammar(依存語法). *範例 >基本的從句結構，可以用名詞短語(NP)和動詞短語(VP)來理解。

 *ParsetreethatusesConstituencygrammariscalledconstituency-basedparsetree. --- ###DependencyGrammar(依存語法) *Itisoppositetotheconstituencygrammar(短語結構文法)andbasedondependencyrelation.ItwasintroducedbyLucienTesniere. *Dependencygrammar(DG)isoppositetotheconstituencygrammarbecauseitlacksphrasalnodes(缺少短語節點). *範例 >**動詞**成為從句結構的中心。

與動詞相連的這些語法單元，稱為依賴項(dependencies)。

 *Parsetreesthatusesdependencygrammariscalleddependency-basedparsetree. --- ###ContextFreeGrammar(CFG) >Contextfreegrammar,alsocalledCFG,isanotationfordescribinglanguagesandasupersetofRegulargrammar.  *DefinitionofCFG *CFGconsistsoffinitesetofgrammarruleswiththefollowingfourcomponents 1.SetofNon-terminals 2.SetofTerminals 3.SetofProductions 4.StartSymbol --- ##貢獻Contribution --- ##挑戰Challenge --- ##參考資源Resources *[Web][成分句法分析&依存句法分析Parsing知識圖譜](https://tw511.com/a/01/6881.html) *[Web][NaturalLanguageProcessing-SyntacticAnalysis](https://www.tutorialspoint.com/natural_language_processing/natural_language_processing_syntactic_analysis.htm) *[Web][Context-FreeGrammarIntroduction-Derivation](https://www.tutorialspoint.com/automata_theory/context_free_grammar_introduction.htm) *[Youtube][leftmostandrightmostderivations](https://www.youtube.com/watch?v=K_aMajzrKF4) *[Youtube][Context-FreeGrammar](https://www.youtube.com/watch?v=Rhqk9HYiB7Q) *[Youtube][ContextFreeGrammar&ContextFreeLanguage](https://www.youtube.com/watch?v=5_tfVe7ED3g) × Signin Email Password Forgotpassword or Byclickingbelow,youagreetoourtermsofservice. SigninviaFacebook SigninviaTwitter SigninviaGitHub SigninviaDropbox SigninviaGoogle NewtoHackMD?Signup