1\u3001error in the scanner: generate an error token and consume the offending character.<\/p>\n
2\u3001error in the parser:<\/p>\n
- \n
- report an error message \u3010\u62a5\u9519\u3011<\/li>\n
- recover from the error and continue parsing (to find as many errors as possible). \u3010\u5c3d\u53ef\u80fd\u591a\u53d1\u73b0\u9519\u8bef\u3011<\/li>\n
- Sometimes, a parser may perform error repair.\u3010\u4fee\u590d\u9519\u8bef\u3011<\/li>\n<\/ul>\n
Context-free Grammars<\/h3>\n
\u4e0a\u4e0b\u6587\u65e0\u5173\u8bed\u6cd5\u4f7f\u7528\u9012\u5f52\uff0c\u662f\u4e00\u79cd\u7f16\u7a0b\u8bed\u8a00\u8bed\u6cd5\u7ed3\u6784\u7684\u89c4\u8303\u3002<\/p>\n
eg:<\/p>\n
exp -> exp op exp | (exp) | number<\/p>\n
op -> + | \u2013 | *<\/p>\n
\u5176\u4e2d:<\/p>\n
number = digit digit*<\/p>\n
digit = 0|1|2|3|4|5|6|7|8|9<\/p>\n
<\/h2>\n
<\/p>\n
Derivations<\/span><\/h2>\n
\nDerivation \u6d3e\u751f<\/h3>\n
\u8bed\u6cd5\u89c4\u5219\u901a\u8fc7\u6d3e\u751f\u6765\u786e\u5b9a\u6807\u8bb0\u7b26\u53f7\u7684\u5408\u6cd5\u5b57\u7b26\u4e32\u3002<\/p>\n
- \n
- \u901a\u8fc7\u8bed\u6cd5\u89c4\u5219\u53f3\u4fa7\u7684\u9009\u9879\u66ff\u6362\u7ed3\u6784\u540d\u79f0\u7684\u5e8f\u5217\u3002<\/li>\n
- \u6d3e\u751f\u4ee5\u5355\u4e2a\u7ed3\u6784\u540d\u79f0\u5f00\u59cb\uff0c\u4ee5\u6807\u8bb0\u7b26\u53f7\u5b57\u7b26\u4e32\u7ed3\u675f\u3002<\/li>\n
- \u5728\u6d3e\u751f\u7684\u6bcf\u4e2a\u6b65\u9aa4\u4e2d\uff0c\u4f7f\u7528\u8bed\u6cd5\u89c4\u5219\u4e2d\u7684\u4e00\u4e2a\u9009\u9879\u8fdb\u884c\u5355\u4e2a\u66ff\u6362\u3002<\/li>\n<\/ul>\n
\u751f\u6210\u8bed\u8a00 L(G) = { s | exp =>* s }<\/h3>\n
1\u3001 G\u8868\u793a\u8868\u8fbe\u5f0f\u8bed\u6cd5
\n2\u3001 s\u8868\u793a\u4efb\u610f\u7684\u6807\u8bb0\u7b26\u53f7\u5b57\u7b26\u4e32\uff08\u6709\u65f6\u79f0\u4e3a\u53e5\u5b50\uff09
\n3\u3001 \u7b26\u53f7=>*\u8868\u793a\u7531\u524d\u9762\u63cf\u8ff0\u7684\u66ff\u6362\u5e8f\u5217\u7ec4\u6210\u7684\u6d3e\u751f\u3002
\n4\u3001 \u8bed\u6cd5\u89c4\u5219\u6709\u65f6\u88ab\u79f0\u4e3a\u4ea7\u751f\u5f0f\uff0c\u56e0\u4e3a\u5b83\u4eec\u901a\u8fc7\u6d3e\u751f\u201c\u4ea7\u751f\u201dL\uff08G\uff09\u4e2d\u7684\u5b57\u7b26\u4e32\u3002<\/p>\n\u7b26\u53f7\uff1a<\/p>\n
\u63a8\u5bfc\u89c4\u5219\uff1a-><\/p>\n
\u5355\u6b65\u63a8\u5bfc\uff1a=><\/p>\n
\u591a\u6b65\u63a8\u5bfc\uff1a=>*<\/p><\/blockquote>\n
\u8d77\u59cb\u7b26\u53f7\u3001\u975e\u7ec8\u7ed3\u7b26\u3001\u7ec8\u7ed3\u7b26<\/h3>\n
\u8d77\u59cb\u7b26\u53f7the start symbol\uff1a\u6700\u4e00\u822c\u7684\u7ed3\u6784\u5217\u5728\u8bed\u6cd5\u89c4\u5219\u7684\u7b2c\u4e00\u4f4d\u3002<\/p>\n
\u975e\u7ec8\u7ed3\u7b26nonterminals\uff1a\u56e0\u4e3a\u5728\u6d3e\u751f\u8fc7\u7a0b\u4e2d\u5b83\u4eec\u603b\u662f\u5fc5\u987b\u88ab\u8fdb\u4e00\u6b65\u66ff\u6362\u3002<\/p>\n
\u7ec8\u7ed3\u7b26terminals\uff1a\u5b57\u6bcd\u8868\u4e2d\u7684\u7b26\u53f7\u79f0\u4e3a\u7ec8\u7ed3\u7b26\uff0c\u56e0\u4e3a\u5b83\u4eec\u7ec8\u6b62\u6d3e\u751f\u3002\u7ec8\u7aef\u901a\u5e38\u662f\u7f16\u8bd1\u5668\u5e94\u7528\u7a0b\u5e8f\u4e2d\u7684tokens\u3002<\/p>\n
left recursive:<\/span> the nonterminal A appears as the first symbol on the right-hand side of the rule defining A.<\/p>\n
right recursive:<\/span> the nonterminal A appears as the last symbol on the right-hand side of the rule defining A.<\/p>\n
Egs:<\/p>\n
\n\n
\n \u89c4\u5219<\/td>\n \u4ea7\u751f\u5f0f<\/td>\n<\/tr>\n \n A -> (A) A |\u00a0\u03b5<\/td>\n <\/td>\n<\/tr>\n \n stmt-sequence -> stmt ; stmt-sequence | stmt<\/p>\n stmt -> s<\/td>\n
L(G)= { s, s;s, s;s;s… }<\/td>\n<\/tr>\n \n stmt-sequence -> stmt ; stmt-sequence | \u03b5<\/p>\n stmt -> s<\/td>\n
L(G’)= { \u03b5, s;, s;s;, s;s;s;,… )<\/td>\n<\/tr>\n \n stmt-sequence -> nonempty-stmt-sequence |\u03b5<\/p>\n nonempty-stmt-sequence -> stmt ;<\/p>\n
nonempty-stmt-sequence | stmt<\/p>\n
stmt -> s<\/td>\n
L(G)= { \u03b5, s, s;s, s;s;s… }<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n \u4fee\u6539\u6587\u6cd5\u7684\u540c\u65f6\u9700\u8981\u6ce8\u610f\u662f\u5426\u6539\u53d8\u4e86\u539f\u6709\u7684\u53e5\u610f\u3002<\/p>\n
<\/p>\n
<\/p>\n
<\/p>\n
Parse trees and abstract syntax<\/h2>\n
\nA parse tree<\/span> corresponding to a derivation is a labeled tree<\/p>\n
- \n
- the interior nodes are labeled by nonterminals,<\/li>\n
- the leaf nodes are labeled by terminals<\/li>\n
- the children of each internal node represent the replacement of the associated nonterminal in one step of the derivation.<\/li>\n<\/ul>\n
<\/h2>\n
Abstract syntax trees<\/h3>\n
1\u3001 \u8fd9\u4e9b\u6811\u8868\u793a\u5b9e\u9645\u6e90\u4ee3\u7801\u4ee4\u724c\u5e8f\u5217\u7684\u62bd\u8c61\uff0c\u5e76\u4e14\u4e0d\u80fd\u4ece\u4e2d\u6062\u590d\u4ee4\u724c\u5e8f\u5217\uff08\u4e0e\u89e3\u6790\u6811\u4e0d\u540c\uff09\u3002<\/p>\n
2\u3001 \u89e3\u6790\u6811\u662f\u5c06\u666e\u901a\u7684\u79f0\u4e3a\u5177\u4f53\u8bed\u6cd5\u7684\u7ed3\u6784\u4e0e\u62bd\u8c61\u8bed\u6cd5\u8fdb\u884c\u6bd4\u8f83\u65f6\u7684\u4e00\u79cd\u8868\u793a\u3002<\/p>\n
3\u3001 \u62bd\u8c61\u8bed\u6cd5\u53ef\u4ee5\u7528\u7c7b\u4f3cBNF\u7684\u7b26\u53f7\u7ed9\u51fa\u5f62\u5f0f\u5b9a\u4e49\uff0c\u5c31\u50cf\u5177\u4f53\u8bed\u6cd5\u4e00\u6837\u3002<\/p>\n
typedef enum {Plus,Minus,Times} OpKind; \r\ntypedef enum {Opk,Constk} ExpKind; \r\ntypedef struct streenode \r\n { ExpKind kind;\t.\r\n OpKind op;\r\n struct streenode *lchild,*rchild;\r\n int val;\r\n } STreeNode;\r\n typedef STreeNode * SyntaxTree; \r\n<\/pre>\n<\/p>\n
<\/p>\n
<\/p>\n
typedef enum {ExpK,StmtK} NodeKind; \r\ntypedef enum {Zero,One} ExpKind; \r\ntypedef enum {IfK,OtherK) StmtKind; \r\ntypedef struct streenode \r\n { NodeKind kind;\r\n ExpKind ekind;\t.\r\n StmtKind skind;\r\n struct streenode *test,*thenpart,*elsepart;\r\n } STreeNode;\r\n typedef STreeNode * SyntaxTree;<\/pre>\n\u4f7f\u7528\u94fe\u8868\u5b58\u50a8\u5b69\u5b50\u3002<\/p>\n
<\/p>\n
<\/p>\n
<\/p>\n
Ambiguous grammmars<\/h2>\n
\nan ambiguous grammar<\/span>: a grammar that generates a string with two distinct parse trees is called an ambiguous grammar. \u4e00\u79cd\u751f\u6210\u5177\u6709\u4e24\u4e2a\u4e0d\u540c\u89e3\u6790\u6811\u7684\u5b57\u7b26\u4e32\u7684\u8bed\u6cd5\u79f0\u4e3a\u4e8c\u4e49\u8bed\u6cd5\u3002<\/p>\n
- \n
- Such a grammar represents a serious problem for a parser.<\/li>\n
- it does not specify precisely the syntactic structure of a program.<\/li>\n<\/ul>\n
\u4e24\u79cd\u57fa\u672c\u65b9\u6cd5\uff1a<\/p>\n
1\u3001\u5728\u6bcf\u79cd\u4e0d\u660e\u786e\u7684\u60c5\u51b5\u4e0b\uff0c\u6307\u5b9a\u54ea\u79cd\u89e3\u6790\u6811\uff08\u6216\u8bed\u6cd5\u6811\uff09\u662f\u6b63\u786e\u7684\u3002\u8fd9\u79cd\u89c4\u5219\u79f0\u4e3a\u6d88\u6b67\u89c4\u5219\u00a0disambiguating rule<\/span>\u3002<\/p>\n
- \n
- \u4f18\u70b9\uff1a\u5b83\u53ef\u4ee5\u7ea0\u6b63\u6b67\u4e49\uff0c\u800c\u4e0d\u4f1a\u6539\u53d8\u8bed\u6cd5\uff08\u4e5f\u53ef\u80fd\u4f7f\u8bed\u6cd5\u590d\u6742\u5316\uff09\u3002<\/li>\n
- \u7f3a\u70b9\uff1a\u8bed\u8a00\u7684\u53e5\u6cd5\u7ed3\u6784\u4e0d\u518d\u4ec5\u4ec5\u7531\u8bed\u6cd5\u7ed9\u51fa\u3002<\/li>\n<\/ul>\n
2\u3001 \u5c06\u8bed\u6cd5\u66f4\u6539\u4e3a\u5f3a\u5236\u6784\u9020\u6b63\u786e\u89e3\u6790\u6811\u7684\u5f62\u5f0f\u3002<\/p>\n
*\u5728\u8fd9\u4e24\u79cd\u65b9\u6cd5\u4e2d\uff0c\u6211\u4eec\u5fc5\u987b\u9996\u5148\u786e\u5b9a\u5728\u4e0d\u660e\u786e\u7684\u60c5\u51b5\u4e0b\u54ea\u4e2a\u6811\u662f\u6b63\u786e\u7684\u3002<\/p>\n
Precedence and associativity<\/h3>\n
\u5c06\u8fd0\u7b97\u7b26\u5206\u7ec4\u4e3a\u5177\u6709\u76f8\u540c\u4f18\u5148\u7ea7\u7684\u7ec4\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u4f18\u5148\u7ea7\uff0c\u6211\u4eec\u5fc5\u987b\u7f16\u5199\u4e0d\u540c\u7684\u89c4\u5219\u3002<\/p>\n
\u4f8b\u5982\uff0c\u4e58\u6cd5\u4f18\u5148\u4e8e\u52a0\u6cd5\u548c\u51cf\u6cd5\u53ef\u4ee5\u6dfb\u52a0\u5230\u6211\u4eec\u7684\u7b80\u5355\u8868\u8fbe\u5f0f\u8bed\u6cd5\u4e2d\uff0c\u5982\u4e0b\u6240\u793a\uff1a<\/p>\n
Precedence\uff1a<\/p>\n
- \n
- exp -> exp addop exp | term<\/li>\n
- addop -> + | –<\/li>\n
- term -> term mulop term| factor<\/li>\n
- mulop -> *<\/li>\n
- factor -> ( exp ) | number<\/li>\n<\/ul>\n
associativity\uff1a<\/p>\n
- \n
- exp -> exp addop exp | term<\/li>\n
- replacing the rule by\n
- \n
- exp -> exp addop term |term (left associative )<\/li>\n
- exp -> term addop exp |term (right associative)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n
The dangling else problem<\/h3>\n
\n\n
\n \u89c4\u5219<\/td>\n \u7528\u4f8b<\/td>\n<\/tr>\n \n statement -> if-stmt | other<\/p>\n if-stmt -> if ( exp ) statement | if ( exp ) statement else statement<\/p>\n
exp -> 0 | 1<\/td>\n
if (0) if (1) other else other<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n This string has the two parse trees.<\/p>\n
\u4fee\u6539\u540e\u4e0d\u518d\u5177\u6709\u4e8c\u4e49\u6027\uff1a<\/p>\n
\n\n
\n \u89c4\u5219<\/td>\n \u7528\u4f8b<\/td>\n<\/tr>\n \n statement -> matched-stmt | unmatched-stmt<\/p>\n matched-stmt -> if ( exp ) matched-stmt else matched-stmt | other<\/p>\n
unmatched-stmt -> if ( exp ) statement | if ( exp ) matched-stmt else unmatched-stmt<\/p>\n
exp -> 0 | 1<\/td>\n
<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
<\/p>\n
\u5176\u4ed6\u89e3\u51b3\u65b9\u6cd5\uff1a<\/p>\n
- \n
- if & end if<\/li>\n
- else & end if<\/li>\n<\/ul>\n
EBNF<\/h3>\n
\u5de6\u53f3\u9012\u5f52\uff1a<\/p>\n
- \n
- A -> \u03b2 { \u03b1 }\u00a0(left recursive)<\/li>\n
- A -> { \u03b1 }\u00a0\u03b2\u00a0(right recursive)<\/li>\n<\/ul>\n
\u53ef\u9009\u8bed\u53e5\uff1a<\/p>\n
- \n
- statement -> if-stmt | other<\/li>\n
- if-stmt -> if ( exp ) statement [ else statement ]<\/li>\n
- exp -> 0 | 1<\/li>\n<\/ul>\n
\u63a8\u5bfc\u4e2d\u79f0\u4e3a\u53e5\u578b\uff08sentential form\uff09\uff0c\u63a8\u5bfc\u7ec8\u7ed3\u79f0\u4e3a\u53e5\u5b50\uff08sentences\uff09\u3002<\/p>\n
<\/p>\n
<\/h1>\n
Top-Down Parsing<\/h1>\n
Top-down parsing<\/h2>\n
\n\u9012\u5f52\u4e0b\u964d\u53e5\u6cd5\u5206\u6790\u7684\u601d\u60f3\uff1a<\/p>\n
- \n
- \u975e\u7ec8\u7aefa\u4f5c\u4e3a\u8fc7\u7a0b\u8bc6\u522ba\u7684\u5b9a\u4e49\u7684\u8bed\u6cd5\u89c4\u5219\uff1b<\/li>\n
- A\u8bed\u6cd5\u7684\u53f3\u4fa7\u6307\u5b9a\u6b64\u8fc7\u7a0b\u7684\u4ee3\u7801\u7ed3\u6784\u3002<\/li>\n<\/ul>\n
\n\n
\n BNF<\/td>\n EBNF<\/td>\n \u7a0b\u5e8f<\/td>\n<\/tr>\n \n <\/td>\n factor \u2192(expr) \u2223 number<\/td>\n Procedure factor<\/p>\n BEGIN<\/p>\n
case token of<\/p>\n
( : match( ( );<\/p>\n
expr;<\/p>\n
match( ));<\/p>\n
number:<\/p>\n
match(number);<\/p>\n
else error;<\/p>\n
end case;<\/p>\n
END factor<\/td>\n<\/tr>\n
\n If-stmt \u2192 if ( exp ) statement \u2223 if ( exp ) statement else statement<\/td>\n If-stmt \u2192 if ( exp ) statement [ else statement]<\/td>\n Procedure IfStmt ;<\/p>\n begin<\/p>\n
match( if);<\/p>\n
match(();<\/p>\n
exp;<\/p>\n
match());<\/p>\n
statement;<\/p>\n
if token = else then<\/p>\n
match ( else);<\/p>\n
statement;<\/p>\n
endif<\/p>\n
end IfStmt;<\/td>\n<\/tr>\n
\n expr \u2192 expr addop term\u2223term<\/td>\n expr \u2192 term {addop term}<\/td>\n Procedure exp;<\/p>\n Begin term;<\/p>\n
while token = + or token = – do<\/p>\n
match(token);<\/p>\n
term;<\/p>\n
End while;<\/p>\n
End exp;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\n
(1) It may be difficult to convert a grammar in BNF into EBNF form;<\/p>\n
(2) It is difficult to decide when to use the choice A \u2192\u03b1 and the choice A \u2192\u03b2;if both \u03b1 and \u03b2 begin with non-terminals. (<\/span>First Sets.) <\/span><\/span><\/p>\n
(3) It may be necessary to know what token legally coming from the non-terminal A, A\u2192\u03b5. (Follow Sets.) <\/span><\/p>\n
(4) It requires computing the First and Follow<\/span> sets in order to detect the errors as early as possible. Such as \u201c)3-2)\u201d, (descend from exp to term to factor) \u5b83\u9700\u8981\u8ba1\u7b97\u7b2c\u4e00\u7ec4\u548c\u7b2c\u4e8c\u7ec4\uff0c\u4ee5\u4fbf\u5c3d\u65e9\u68c0\u6d4b\u9519\u8bef\u3002\u4f8b\u5982\u201c3-2\uff09\u201d\uff0c\uff08\u4eceexp\u5230term\u518d\u5230factor\uff09<\/p>\n
<\/h2>\n
LL(k) grammars<\/h2>\n
\nLL\uff081\uff09\u89e3\u6790\u4f7f\u7528\u663e\u5f0f\u5806\u6808\u800c\u4e0d\u662f\u9012\u5f52\u8c03\u7528\u6765\u6267\u884c\u89e3\u6790\u3002<\/p>\n
<\/h2>\n","protected":false},"excerpt":{"rendered":"
Context-Free Grammars and Parsing Context Free Gra […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[37,16],"tags":[],"_links":{"self":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/1433"}],"collection":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1433"}],"version-history":[{"count":5,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/1433\/revisions"}],"predecessor-version":[{"id":1438,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/1433\/revisions\/1438"}],"wp:attachment":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1433"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1433"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1433"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}