《英语语法描述》PPT课件.ppt

资源描述

《《英语语法描述》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《英语语法描述》PPT课件.ppt（23页珍藏版）》请在三一办公上搜索。

1、Parsing,The scanner recognizes words The parser recognizes syntactic unitsParser operations:Check and verify syntax based on specified syntax rulesReport errorsBuild IRAutomation:The process can be automated,Parsing,Check and verify syntax based on specified syntax rulesAre regular expressions suffi

2、cient for describing syntax?Example 1:Infix expressionsExample 2:Nested parentheses We use Context-Free Grammars(CFGs)to specify context-free syntax.A CFG describes how a sentence of a language may be generated.Example:Use this grammar to generate the sentence mwa ha ha ha!,EvilLaugh mwa EvilCackle

3、EvilCackle ha EvilCackle EvilCackle ha!,CFGs,A CFG is a quadruple(N,T,R,S)where N is the set of non-terminal symbolsT is the set of terminal symbolsS N is the starting symbolR N(NT)*is a set of rulesExample:The grammar of nested parenthesesG=(N,T,R,S)where N=ST=(,)R=S(S),SSS,S,Derivations,The langua

4、ge described by a CFG is the set of strings that can be derived from the start symbol using the rules of the grammar.At each step,we choose a non-terminal to replace.,S(S)(SS)(S)S)()S)()(S)()(S)()(),derivation,sentential form,This example demonstrates a leftmost derivation:one where we always expand

5、 the leftmost non-terminal in the sentential form.,Derivations and parse trees,We can describe a derivation using a graphical representation called parse tree:the root is labeled with the start symbol,Seach internal node is labeled with a non-terminalthe children of an internal node A are the right-

6、hand side of a production Aeach leaf is labeled with a terminalA parse tree has a unique leftmost and a unique rightmost derivation(however,we cannot tell which one was used by looking at the tree),Derivations and parse trees,So,how can we use the grammar described earlier to verify the syntax of()(

7、)?We must try to find a derivation for that string.We can work top-down(starting at the root/start symbol)or bottom-up(starting at the leaves).Careful!There may be more than one grammars to describe the same language.Not all grammars are suitable,Problems in parsing,Consider S if E then S else S|if

8、E then SWhat is the parse tree for if E then if E then S else SThere are two possible parse trees!This problem is called ambiguityA CFG is ambiguous if one or more terminal strings have multiple leftmost derivations from the start symbol.,S,if E then S,S,if E then S,if E then S else S,if E then S el

9、se S,Ambiguity,There is no general algorithm to tell whether a CFG is ambiguous or not.There is no standard procedure for eliminating ambiguity.Some languages are inherently ambiguous.In those cases,any grammar we come up with will be ambiguous.,Ambiguity,In general,we try to eliminate ambiguity by

11、hElse else EnoElse,Top-down parsing,Main idea:Start at the root,grow towards leavesPick a production and try to match inputMay need to backtrackExample:Use the expression grammar to parse x-2*y,Grammar problems,Because we try to generate a leftmost derivation by scanning the input from left to right

12、,grammars of the form A A x may cause endless recursion.Such grammars are called left-recursive and they must be transformed if we want to use a top-down parser.,Left recursion,A grammar is left recursive if for a non-terminal A,there is a derivation A+AThere are three types of left recursion:direct

13、(A A x)indirect(A B C,B A)hidden(A B A,B),Left recursion,To eliminate direct left recursion replace A A1|A2|.|Am|1|2|.|n with A 1B|2B|.|nB B 1B|2B|.|mB|,Left recursion,How about this:S EE E+TE TT E-TT id,There is direct recursion:EE+TThere is indirect recursion:TE+T,ET,Algorithm for eliminating indi

14、rect recursionList the nonterminals in some order A1,A2,.,Anfor i=1 to n for j=1 to i-1 if there is a production AiAj,replace Aj with its rhs eliminate any direct left recursion on Ai,Eliminating indirect left recursion,S EE E+TE TT E-TT FF E*FF id,i=S,ordering:S,E,T,F,S EE E+TE TT E-TT FF E*FF id,i

16、 S else S|if E then SWhich of the two productions should we use to expand non-terminal S when the next token is if?We can solve this problem by factoring out the common part in these rules.This way,we are postponing the decision about which rule to choose until we have more information(namely,whethe

17、r there is an else or not).This is called left factoring,Left factoring,A 1|2|.|n|becomesA B|B 1|2|.|n,Grammar problems,A symbol XV is useless ifthere is no derivation from X to any string in the language(non-terminating)there is no derivation from S that reaches a sentential form containing X(non-r

18、eachable)Reduced grammar=a grammar that does not contain any useless symbols.,Useless symbols,In order to remove useless symbols,apply two algorithms:First,remove all non-terminating symbolsThen,remove all non-reachable symbols.The order is important!For example,consider S+X where contains a non-ter

19、minating symbol.What will happen if we apply the algorithms in the wrong order?Concrete example:S AB|a,A a,Useless symbols,Example,Initial grammar:S AB|CAA aB CB|ABC cB|bD aD|d,Algorithm 1(terminating symbols):A is in because of A aC is in because of C bD is in because of D dS is in because A,C are in and S AC,Useless symbols,Example continued,After algorithm 1:S CAA aC bD aD|d,Algorithm 2(reachable symbols):S is in because it is the start symbolC and A are in because S is in and S CA,Final grammar:S CAA aC b,

展开阅读全文