※ 引述《bnm51315 (La-La)》之铭言： : 最近看书看到"程式语言"这章 : 其中有提到代数运算式语法图和语法图所建的字串剖析树 ^^^^^^^^^^ ^^^^^^^^^^ expression(expr.) parse tree : 但是看了半天 : 书上没有解释剖析树要怎麽转换、怎麽看 : 所以想请问各位 : 这种东西要怎麽去做转换以及怎麽去解析... 先说，我对这个也不是很了解，有讲错的地方麻烦板上高手更正。 简单来说， 就是像在实做编译器等需要「解析语法」的地方， 他内部会有一个判别的语法(grammar), 若是可以依据这个 grammar 的推展来得到最後的 expr.， 就可判断此 expr. 为合乎语法 e.g. a + b * c - d / e 合乎语法 a + b c - d 不合乎语法 举一个简单的 grammar 可能长这样: <expr> -> <expr> + <term> | <expr> - <term> | <term> (1.1 - 1.3) <term> -> <term> * <fact> | <term> / <fact> | <fact> (2.1 - 2.3) <fact> -> <nums> | (<expr>) (3.1, 3.2) <nums> -> 0 | 1 | 2 | ... | 8 | 9 (4.1 - 4.10) 每一个用 < > 括起来的都是 variable(non-terminal)，意思就是还可以再转换 最後的 0, 1, ... , 9, +, -, *, / 是 terminal 上面每一条 grammar 代表 [左边的 valuable] 可以转换成 [右边的表示式] 而 | 就是 「或」 的意思，表示从中选一个， 因此我把上面每一种转换的可能都编上号码(1.1 - 4.10)，方便说明 假设现在我要判断 5 * (6 - 1) 是不是一个 expr. 那麽可以试着推推看： <expr> = <term> 1.3 = <term> * <fact> 2.1 = <fact> * <fact> 2.3 = <nums> * <fact> 3.1 = 5 * <fact> 4.6 = 5 * (<expr>) 3.2 = 5 * (<expr> - <term>) 1.2 = 5 * (<term> - <term>) 1.3 = 5 * (<fact> - <term>) 2.3 = 5 * (<nums> - <term>) 3.1 = 5 * ( 6 - <term>) 4.7 = 5 * ( 6 - <fact>) 2.3 = 5 * ( 6 - <nums>) 3.1 = 5 * ( 6 - 1 ) 4.2 至於 paser tree 就是上面用式子推导的过程，改用 tree 的型态来表示，换汤不换药 <expr> | <term> 1.3 / | \ <term> * <fact> 2.1 | | | <fact> * <fact> 2.3 | | | <nums> * <fact> 3.1 | | \ 5 * <fact> 4.6 | | \ 5 * (<expr>) 3.2 | | / | \ 5 * (<expr> - <term>) 1.2 | | | | | 5 * (<term> - <term>) 1.3 | | | | | 5 * (<fact> - <term>) 2.3 | | | | | 5 * (<nums> - <term>) 3.1 | | | | | 5 * ( 6 - <term>) 4.7 | | | | | 5 * ( 6 - <fact>) 2.3 | | | | | 5 * ( 6 - <nums>) 3.1 | | | | | 5 * ( 6 - 1 ) 4.2 因此，不管从式子推导，或是 parse tree， 我们都可知 5 * (6 - 1) 合乎我们上面所给定那个 grammar 然而你可以发现像是 2(4 * 7 / 3) 这样是推导不出来的， 它并不属於我所给的这个 grammar 所定义的语言(language) （但是仍有可能有另外一个 grammar 能够解析它） -- 我印象中去年不管考试还是写考古题， 好像都没碰过这种问题啊。 建议有个大致的认识就好，不用太钻研 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 220.133.2.239 ※ 编辑: rainphiz 来自: 220.133.2.239 (03/31 14:00)