{"id":1472,"date":"2020-03-18T18:50:31","date_gmt":"2020-03-18T10:50:31","guid":{"rendered":"http:\/\/149.129.74.185\/?p=1472"},"modified":"2020-03-18T21:01:22","modified_gmt":"2020-03-18T13:01:22","slug":"%e7%bc%96%e8%af%91%e5%8e%9f%e7%90%86-week-4-note","status":"publish","type":"post","link":"http:\/\/www.magicmipamipa.com\/?p=1472","title":{"rendered":"[\u7f16\u8bd1\u539f\u7406] Week 4 Note"},"content":{"rendered":"

LL(1) Parsing<\/h2>\n
\n

\u91c7\u7528\u663e\u5f0f\u7684\u5806\u6808\uff0c\u4ece\u4e0a\u800c\u4e0b\uff0c\u4ece\u5f00\u59cb\u7b26\u53f7\u5f00\u59cb\u63a8\u5bfc\u5230\u7ec8\u7ed3\u7b26\u3002<\/p>\n

Example<\/strong><\/span><\/p>\n

<\/p><\/blockquote>\n

\u9700\u8981\u9009\u62e9\u6b63\u786e\u7684\u5339\u914d\u65b9\u5f0f\uff0c\u5982\u4f55\u505a\u5230\uff1f<\/p>\n

*\u53cd\u5e8f\u538b\u5165\u5806\u6808<\/p>\n

Parsing Table:(\u4e0d\u9700\u8981\u7a0b\u5e8f\u4e4b\u95f4\u7684\u9012\u5f52\u8c03\u7528)<\/p>\n

<\/p>\n

 <\/p>\n

Parsing Table and Algorithm<\/h3>\n

\u6587\u6cd5\u4e0a\u53ef\u4ee5\u51fa\u73b0\u5728A\u540e\u9762\u7684\u7b26\u53f7<\/p>\n

The constructing-process of the above table:<\/p>\n

\uff081\uff09 \u5bf9\u4e8e\u751f\u4ea7\uff1aS\u2192\uff08S\uff09S\uff0c\u6761\u76eeM[S\uff0c\uff08]
\n\uff082\uff09 \u5bf9\u4e8e\u751f\u4ea7\uff1aS\u2192\u03b5\uff0cS$=>*\uff08S\uff09S$\u3002\u5176\u4e2da=\uff09\u6216a=$\u3002\u56e0\u6b64\uff0c\u5c06\u9009\u62e9S\u2192\u03b5\u52a0\u5230M[S\uff0c\uff09]\u548cM[S\uff0c$]\u4e2d\u3002<\/p>\n

Definition of LL(1) Grammar:<\/p>\n

    \n
  • A grammar is an LL(1) grammar if the associated LL(1) parsing table has at most one production in each table entry.<\/li>\n
  • An LL(1) grammar cannot be ambiguous.<\/span><\/li>\n<\/ul>\n

    LL(1) \u4ee3\u7801\uff1a<\/p>\n

    push the start symbol onto the top the parsing stack;\r\nwhile the top of the parsing stack \u2260 $ and the next   \r\n     input token \u2260 $ do\r\n    if the top of the parsing stack is terminal a \r\n          and the next input token = a\r\n    then (* match *)\r\n         pop the parsing stack;\r\n        advance the input;\r\n    else if the top of the parsing stack is non-terminal A\r\n      and the next input token is terminal a\r\n      and parsing table entry M[A,a] contains production A\u2192X1X2\u2026Xn\r\nthen (* generate *)\r\n         pop the parsing stack;\r\n         for i:=n downto 1 do\r\n                push Xi onto the parsing stack;\r\n    else error;\r\n if the top of the parsing stack = $\r\n    and the next input token = $\r\n then accept\r\nelse error. \r\n\r\n<\/pre>\n
    Example\uff1a<\/p>\n
      \n
    • statement \u2192 if-stmt | other<\/li>\n
    • if-stmt \u2192 if (exp) statement else-part<\/li>\n
    • else-part \u2192 else statement | \u03b5<\/li>\n
    • exp \u2192 0 | 1<\/li>\n<\/ul>\n
      <\/p>\n
       <\/p>\n
      left Recursion Removal and Left Factoring<\/h3>\n
      \u3010\u76f4\u63a5\u5de6\u9012\u5f52\u3011<\/p>\n
      Case 1: A \u2192 A\u03b1| \u03b2 \u66ff\u6362\u4e3a\uff1a<\/p>\n
        \n
      • A \u2192 \u03b2A\u2019<\/li>\n
      • A\u2019 \u2192 \u03b1A\u2019| \u03b5<\/li>\n
      • \u5de6\u9012\u5f52\u53d8\u4e3a\u4e86\u53f3\u9012\u5f52\u3002<\/li>\n<\/ul>\n
        Case 2:A \u2192 A \u03b11 | A \u03b12 | \u2026 | A \u03b1n |\u03b21|\u03b22|\u2026|\u03b2m<\/p>\n
        \u6bcf\u4e2a\u03b1\u90fd\u4e0d\u7b49\u4e8e\u7a7a\uff0c\u6bcf\u4e2a\u03b2\u90fd\u4e0d\u4e00\u4ee5A\u5f00\u5934\u3002<\/p>\n
        \u66ff\u6362\u4e3a\uff1a<\/p>\n
          \n
        • A \u2192\u03b21A\u2019|\u03b22A\u2019| \u2026|\u03b2mA\u2019<\/li>\n
        • A\u2019 \u2192 \u03b11A\u2019| \u03b12A\u2019| \u2026 | \u03b1nA\u2019| \u03b5<\/li>\n
        • \u5b9e\u73b0\u4e86\u4efb\u610f\u591a\u76f4\u63a5\u5de6\u9012\u5f52\u7684\u6539\u9020\u3002<\/li>\n<\/ul>\n
           <\/p>\n
          \u3010\u7b80\u6d01\u3001\u76f4\u63a5\u5de6\u9012\u5f52\u3011<\/p>\n
          \u4e00\u4e2a\u6587\u6cd5\u6d88\u9664\u5de6\u9012\u5f52\u7684\u6761\u4ef6\uff1a<\/p>\n
            \n
          • \u4e0d\u542b\u4ee5\u03b5\u4e3a\u53f3\u90e8\u7684\u4ea7\u751f\u5f0f<\/li>\n
          • \u4e0d\u542b\u56de\u8defA=>+A<\/li>\n<\/ul>\n
            \u628a\u5019\u9009\u4e2d\u5f00\u5934\u7684\u975e\u7ec8\u7ed3\u7b26\u66ff\u6362\u4e3a\u5b83\u7684\u5b9a\u4e49\uff0c\u4e0d\u65ad\u66ff\u6362\u3002<\/p>\n
            <\/p>\n
            3. \u5316\u7b80\u6d88\u9664\u6c38\u8fdc\u65e0\u6cd5\u5230\u8fbe\u7684\u89c4\u5219\u3002<\/p>\n
             <\/p>\n
            Left factoring<\/h4>\n
              \n
            • \u5f15\u5165\u975e\u7ec8\u7ed3\u7b26\uff0c\u63d0\u53d6\u5de6\u516c\u56e0\u5b50<\/li>\n<\/ul>\n
              <\/h3>\n
              Syntax Tree Construction<\/h3>\n
              How to compute the arithmetic value of the expression.<\/p>\n
              (1)\u00a0 Use a separate stack to store the intermediate values of the computation, called the value stack;<\/p>\n
              (2)\u00a0 Schedule two operations on that stack: A push of a number; The addition of two numbers.<\/p>\n
              (3)\u00a0PUSH<\/span> can be performed by the match procedure, and<\/p>\n
              (4) ADDITION<\/span> should be scheduled on the stack, by pushing a special symbol (such as #) on the parsing stack.<\/p>\n
                \n
              • the rule for E\u2019:\n
                  \n
                • E \u2192 n E\u2019<\/li>\n
                • E\u2019 \u2192+n#E\u2019|\u03b5<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n
                  #\u4ee3\u8868\u8f93\u5165\u4e32\u7684\u7ed3\u675f\u3002<\/p>\n
                  <\/h2>\n
                  First and Follow Sets<\/h2>\n
                  \n
                  \u3010\u6d88\u9664\u56de\u6eaf\u3011<\/p>\n
                  First Sets<\/h3>\n
                  Definition:<\/p>\n
                  Let X be a grammar symbol ( a terminal or non-terminal) or \u03b5. Then First(X) is a set of terminals or \u03b5, which is defined as follows:<\/p>\n
                  1. If X is a terminal or \u03b5, then First(X) = {X};<\/p>\n
                  2. If X is a non-terminal, then for each production choice X\u2192X1 X2 \u2026 Xn, First(X) contains First(X1)-{\u03b5}. if for some i<n, all the sets First(X1)\u2026.First(Xi) contain \u03b5 ,then First(X) also contains First(Xi+1)- {\u03b5}. If all the set First(X1)\u2026.First(Xn) contain \u03b5, the First(X) contains \u03b5.<\/p>\n
                  <\/p>\n
                  Let \u03b1 be a string of terminals and non-terminals, X1X2\u2026Xn. First(\u03b1) is defined as follows:<\/p>\n
                  1.First(\u03b1) contains First(X1)-{\u03b5};<\/p>\n
                  2.For each i=2,\u2026,n, if for all k=1,..,i-1, First(Xk) contains \u03b5, then First(\u03b1) constains First(Xk)-{\u03b5}.<\/p>\n
                  3. If all the set First(X1)..First(Xn) contain \u03b5, the First(\u03b1) contains \u03b5.<\/p>\n
                  Example:<\/p>\n
                  Grammar for statement sequences:<\/p>\n
                  stmt-sequence \u2192stmt<\/p>\n
                  stmt-seq\u2019 stmt-seq\u2019 \u2192; stmt-sequence|\u03b5<\/p>\n
                  stmt\u2192s<\/p><\/blockquote>\n
                  The First sets are as follows:<\/p>\n
                  First(stmt-sequence)={s}<\/p>\n
                  First(stmt-seq\u2019)={;, \u03b5}<\/p>\n
                  First(stmt)={s}<\/p>\n
                  <\/p>\n
                  Follow Sets<\/h3>\n
                  Given a non-terminal A, the set Follow(A) is defined as follows.<\/p>\n
                  (1) if A is the start symbol, the $ is in the Follow(A).<\/p>\n
                  (2) if there is a production B\u2192 \u03b1A\u03b3, then First(\u03b3)-{\u03b5} is in Follow(A).<\/p>\n
                  (3) if there is a production B\u2192 \u03b1A\u03b3, such that \u03b5 in First(\u03b3), then Follow(A) contains Follow(B).<\/p>\n
                  <\/p>\n
                  <\/p>\n
                  Note: (1)The symbol $ is used to mark the end of the input.<\/p>\n
                  (2)The empty \u201cpseudotoken\u201d \u03b5 is never an element of a follow set.<\/p>\n
                  (3)Follow sets are defined only for non-terminal.<\/p>\n
                   <\/p>\n
                  LL(1)\u6587\u6cd5\u5224\u5b9a\uff1a<\/h4>\n
                  <\/p>\n
                   <\/p>\n
                  Follow sets work \u201con the right\u201d in production while First sets work \u201con the left\u201d in the production.<\/p>\n
                  Given a grammar rule A \u2192\u03b1B, Follow(B) will contain Follow(A),the opposite of the situation for first sets, if A \u2192B\u03b1, First(A) contains First(B),except possibly for \u03b5.<\/p>\n","protected":false},"excerpt":{"rendered":"
                  LL(1) Parsing \u91c7\u7528\u663e\u5f0f\u7684\u5806\u6808\uff0c\u4ece\u4e0a\u800c\u4e0b\uff0c\u4ece\u5f00\u59cb\u7b26\u53f7\u5f00\u59cb\u63a8\u5bfc\u5230\u7ec8\u7ed3\u7b26\u3002 Example  […]<\/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\/1472"}],"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=1472"}],"version-history":[{"count":3,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/1472\/revisions"}],"predecessor-version":[{"id":1475,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/1472\/revisions\/1475"}],"wp:attachment":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1472"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1472"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1472"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}