際際滷

際際滷Share a Scribd company logo

Tmpa-2014. table-based GLL parsing.

Semyon Grigorev
Semyon Grigorev

Generalized LL parsing algorithm and it's modification for migration from full code generation to GLL table generation are described. Also we explain correspondence between GLL, GLR and static analysis of string embedded languages.

1 of 20
Download to read offline
亠亢亟仆舒仂亟仆舒 仆舒仆仂-仗舒从亳亠从舒 从仂仆亠亠仆亳: 仆仄亠仆 亳 仄亠仂亟 舒仆舒仍亳亰舒 仗仂亞舒仄仄, TMPA-2014 14-15 仆仂磡 2014, 亞. 仂仂仄舒, 个 弍仂弍仆仆亶 舒弍仍亳仆亶 LL-舒仆舒仍亳亰 于仂: 舒亞仂亰亳仆舒 仆舒舒亳 舒弍仂舒仂亳 JetBrains 仆舒 舒亠仄舒亳从仂-亠舒仆亳亠从仂仄 舒从仍亠亠 弌舒仆从-亠亠弍亞从仂亞仂 亞仂亟舒于亠仆仆仂亞仂 仆亳于亠亳亠舒 15 仆仂磡 2014亞. 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 1 / 20
于亠亟亠仆亳亠 于仂仄舒亳亠从亳亶 舒仆舒仍亳亰 从仂亟舒 从仂仄仗亳仍仂 于亠亳亳从舒仂 亠亟于舒 舒仆舒仍亳亰舒 仍 舒仆舒仍亳亰舒 从仂亟舒 仆亠仂弍仂亟亳仄仂 仗仂仍亳 亠亞仂 从仆仂亠 仗亠亟舒于仍亠仆亳亠 舒弍舒从仆仂亠 亳仆舒从亳亠从仂亠 亟亠亠于仂 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 2 / 20
仂亠仆仆亠 磶从亳 IF @X = @Y SET @TABLE = #table1 ELSE SET @TABLE = table2 EXECUTE (SELECT x FROM + @TABLE + WHERE ISNULL(n,0) > 1) JavaScript 于 Java String script = "function hello(name) print(Hello, + name); "; engine.eval(script); Invocable inv = (Invocable) engine; inv.invokeFunction("hello", "Scripting!!!" ); 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 3 / 20
弍舒从仆亶 舒仆舒仍亳亰 于仂: Kyung-Goo Doh, Hyunha Kim, David A. Schmidt 仆舒仍亳亰 仗仂仂从舒 亟舒仆仆 + LR-舒仆舒仍亳亰 亟仍 仂弍舒弍仂从亳 仍仂亢仆仂亞仂 (仆亠仍亳仆亠亶仆仂亞仂) 于仂亟舒 仍 从舒亢亟仂亞仂 于舒亢亠仆亳 仂亳 舒仗仗仂从亳仄舒亳 仄仆仂亢亠于舒 于亠 亠亞仂 亰仆舒亠仆亳亶, 仆舒亟 从仂仂仂亶 仗仂亳亰于仂亟亳 亳仆舒从亳亠从亳亶 舒仆舒仍亳亰 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 4 / 20
亳仄亠 IF @X = @Y SET @TABLE = #table1 ELSE SET @TABLE = table2 EXECUTE (SELECT x FROM + @TABLE + WHERE ISNULL(n,0) > 1) 仆仂亢亠于仂 亰仆舒亠仆亳亶: {SELECT x FROM #table1 WHERE ISNULL(n,0) > 1 ; SELECT x FROM table2 WHERE ISNULL(n,0) > 1} 仗仗仂从亳仄舒亳: 1 2 "SELECT x FROM " 3 "#table1" "table2" 4 " WHERE ISNULL(n,0) > 1" 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 5 / 20
弍舒从仆亶 舒仆舒仍亳亰 亳亞亳仆舒仍仆亶 仗仂亟仂亟: LALR-舒弍仍亳 仍舒弍仂舒仂亳亳 JetBrains: 仂弍仂弍仆仆亶 LR 仂亟亟亠亢从舒 仗仂亳亰于仂仍仆 弌-亞舒仄仄舒亳从 仂弍仍亠仄舒: 亟亳舒亞仆仂亳从舒 仂亳弍仂从 舒亟亠亢亟舒 仆舒 仂弍仂弍仆仆亶 LL-舒仆舒仍亳亰: 仂仂亠亠 从舒亠于仂 亟亳舒亞仆仂亳从亳 仂亳弍仂从 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 6 / 20
弌亳仆舒从亳亠从亳亶 舒仆舒仍亳亰 亳仂亟亳亶 弌从舒 舒仆舒仍亳亰舒仂舒 亳仄亠亠 亠仆 于磶 亞舒仄仄舒亳从仂亶, 仂 仗仂舒亠 仗仂仆亳仄舒仆亳亠 亠亞从仂 亳 弍仂 仄仂亞 弍 仆舒仗亳舒仆 于仆 丱仂仂舒 亟亳舒亞仆仂亳从舒 仂亳弍仂从 仂亢舒仍亠仆亳, 仂弍舒弍舒于舒亠 亰从亳亶 从仍舒 仂弍舒弍舒于舒亠仄 磶从仂于 仂仂亟亳亶 舒亳磳 从仍舒 仂弍舒弍舒于舒亠仄 磶从仂于 仂仍亠亠 仍仂亢仆舒 从舒 仗舒亠舒 弌仍仂亢仆仂亳 亟亳舒亞仆仂亳从仂亶 仂亳弍仂从 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 7 / 20
弍仂弍仆仆亶 舒仆舒仍亳亰 Generalized LR (GLR) 仗亠于亠 仗亠亟仍仂亢亠仆 丐仂仄亳仂亶 弌亠于亠 仄仆仂亢亠于仂 仄仂亟亳亳从舒亳亶 弌仍仂亢仆舒 亟仍 仂仍舒亟从亳 从舒 舒仆舒仍亳亰舒仂舒 Generalized LL (GLL) Elizabeth Scott, Adrian Johnstone, 2010 仂亟亟亠亢从舒 于亠 弌-亞舒仄仄舒亳从 (仍亠于舒 亠从亳, 从舒 仍亠于舒 亠从亳) 舒仍亠亟亠 仗亠亳仄亠于舒 仆亳仂亟亳 舒仆舒仍亳亰舒仂仂于 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 8 / 20
亳仆亳仗 舒弍仂 亳 于仂亰仆亳从仆仂于亠仆亳亳 仆亠仂亟仆仂亰仆舒仆仂亠亶 舒仄舒亳于舒ﾑ 于亠 于仂亰仄仂亢仆亠 于舒亳舒仆 舒亰弍仂舒 亠于仍亠仆亳亠 亠从舒: 亟仍 从舒亢亟仂亞仂 于舒亳舒仆舒 仂亰亟舒 于仂亶 亠从 亠亰仍舒 舒弍仂: 仍亠 舒亰弍仂舒 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 9 / 20
弌从 亟舒仆仆 舒 从舒亢亟亶 于舒亳舒仆 舒亰弍仂舒 于仂亶 亠从 亳 亟亠亠于仂 亟仂仂亞仂 Graph Structured Stack (GSS) Shared Packed Parsing Forest (SPPF) 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 10 / 20
GSS 仂亰于仂仍磳 从仂仄弍亳仆亳仂于舒 亠从亳 于 从仂仄仗舒从仆 从 亳 于仂亰仆亳从仆仂于亠仆亳亳 从仂仆仍亳从舒 亠从 舒亰于亠于仍磳 亠 于亠亳仆 舒仆 于 亠亟亳仆于亠仆仆仂仄 从亰亠仄仗仍亠 从仍亠亶从舒 于舒亳舒仆仂于 舒亰弍仂舒 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 11 / 20
GSS: 仗亳仄亠 S1, 0 S0, 0 bottom S1, 1 S2, 1 S1, 0 S0, 0 bottom S1, 2 S3, 1 S2, 1 S1, 0 S0, 0 bottom S1, 1 S2, 1 S1, 2 S3, 1 S1, 0 S0, 0 bottom 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 12 / 20
SPPF 亠亠亳仗仂仍亰仂于舒仆亳亠 亰仍仂于 丐亳仗 亰仍仂于: Nonterminal symbol nodes Terminal symbol nodes Packed nodes GLL 亠 亟仂仗仂仍仆亳亠仍仆亠: Intermidiate nodes 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 13 / 20
SPPF: 仗亳仄亠 舒仄仄舒亳从舒: strat s; s ss|B 仂亟: B B B prod 2 n s prod 0 n s n s prod 0 prod 1 n s n s prod 1 prod 1 t B t B t B prod 2 n s prod 0 n s n s prod 1 t B prod 0 n s n s prod 1 prod 1 t B t B prod 2 n s prod 0prod 0 n s n sn s n s prod 0 prod 1 prod 1 t B n s prod 1 prod 0 t B t B 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 14 / 20
GLL-舒仆舒仍亳亰舒仂 仆舒仍亳亰舒仂 仂仂亳 亳亰 仆舒弍仂舒 仆从亳亶 仍 从舒亢亟仂亶 舒仍亠仆舒亳于 亞亠仆亠亳亠 仂亟亠仍仆舒 仆从亳, 仗舒于仍亠仆亳亠 仄亠亢亟 从仂仂仄亳 仗亠亠亟舒 仗仂仄仂 从仂仄舒仆亟 goto() 亠从仂仂亠 goto() 仄仂亞 亳仄亠 仆亠从仂仍从仂 亠仍亠于 仄亠仂从 (仆亠仂亟仆仂亰仆舒仆仂亳 于 亞舒仄仄舒亳从亠) 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 15 / 20
亠从亳仗仂, 仄仆仂亢亠于舒 亠从亳仗仂 (L, s, i, t) L 仄亠从舒 s 于亠亳仆舒 亠从舒 i 仗仂亰亳亳 于仂 于仂亟仆仂仄 仗仂仂从亠 t 从仂亠仆 仂仂于亠于ﾑ亠亞仂 仗仂亟亟亠亠于舒 亠亠亟 亟亠从亳仗仂仂于 R 仂弍仍亠仄舒: 从仂仍亳亠于仂 亟亠从亳仗仂仂于 仄仂亢亠 从仗仂仆亠仆舒仍仆仂 亰舒于亳亠 仂 于仂亟舒, 仂亰亟舒仆亳亠 仗仂于仂仆 仗亳 仍亠于仂亶 亠从从亳亳 亳从仍 亠亠仆亳亠: U 仄仆仂亢亠于仂 亢亠 仂亰亟舒仆仆 亟亠从亳仗仂仂于 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 16 / 20
仗亳舒仆亳亠 (L, i) 仆舒 于亠亳仆舒 亠从舒 丼舒亳 亢亠 仗仂仂亠仆仆仂亞仂 亟亠亠于舒 舒仆 仆舒 弍舒 亠从舒 (T|N, j, i) 亠仄亳仆舒仍仆亶 亳 仆亠亠仄亳仆舒仍仆亶 亰亠仍 亟亠亠于舒 (X = x1x2 揃 x3x4, j, i) 仗仂仄亠亢仂仆亠 亠亶从亳 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 17 / 20
仂亰仄仂亢仆亠 亳舒亳亳 亠亠亟 亠仄亳仆舒仍仂仄: 于亠仍亳亳 仗仂亰亳亳 于仂 于仂亟仆仂仄 仗仂仂从亠, 仂亰亟舒 亠仄亳仆舒仍仆亶 亰亠仍 亟亠亠于舒 亠亠亟 仆亠亠仄亳仆舒仍仂仄: 仂亰亟舒 于亠亳仆 亠从舒, 亰舒仗亳舒 仆仂于亶 亟亠从亳仗仂 舒于亳仍仂 亰舒从仂仆亳仍仂 亳亰于仍亠 于亠亳仆 仂 亠从舒 仂亰亟舒 仆仂于亶 亟亠从亳仗仂 亳仗仂仍亰仂于舒仆亳亠仄 仄亠从亳, 亰舒仗亳舒仆仆仂亶 于 于亠亳仆亠 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 18 / 20
丐舒弍仍亳仆亶 舒仆舒仍亳亰 弍仂 舒仍亠仆舒亳于 仗仂亳仂亟亳 亳仗仂仍亰仂于舒仆亳亠仄 LL-舒弍仍亳 亠从亳 亰舒仄亠仆亠仆 仆舒 仗仂亰亳亳 于 亞舒仄仄舒亳从亠 亳 舒仆亳 仗舒舒 亳亠仍 仍亳 于亟亠仍亠仆 仂弍亳亠 亳舒亳亳: 仗仂亠 舒亰弍仂舒 仂亠于仍磳 仗仂仄仂 仗舒 于亰舒亳仄仆仂亠从亳于仆 仆从亳亶 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 19 / 20
仂仆舒从仆舒 亳仆仂仄舒亳 舒亞仂亰亳仆舒 仆舒舒亳: ragozina.anastasiya@gmail.com 亳亞仂亠于 弌亠仄仆: Semen.Grigorev@jetbrains.com 仂亟仆亶 从仂亟 YaccConstructor: http://recursive-ascent.googlecode.com 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 20 / 20

More Related Content

Tmpa-2014. table-based GLL parsing.

  • 1. 亠亢亟仆舒仂亟仆舒 仆舒仆仂-仗舒从亳亠从舒 从仂仆亠亠仆亳: 仆仄亠仆 亳 仄亠仂亟 舒仆舒仍亳亰舒 仗仂亞舒仄仄, TMPA-2014 14-15 仆仂磡 2014, 亞. 仂仂仄舒, 个 弍仂弍仆仆亶 舒弍仍亳仆亶 LL-舒仆舒仍亳亰 于仂: 舒亞仂亰亳仆舒 仆舒舒亳 舒弍仂舒仂亳 JetBrains 仆舒 舒亠仄舒亳从仂-亠舒仆亳亠从仂仄 舒从仍亠亠 弌舒仆从-亠亠弍亞从仂亞仂 亞仂亟舒于亠仆仆仂亞仂 仆亳于亠亳亠舒 15 仆仂磡 2014亞. 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 1 / 20
  • 2. 于亠亟亠仆亳亠 于仂仄舒亳亠从亳亶 舒仆舒仍亳亰 从仂亟舒 从仂仄仗亳仍仂 于亠亳亳从舒仂 亠亟于舒 舒仆舒仍亳亰舒 仍 舒仆舒仍亳亰舒 从仂亟舒 仆亠仂弍仂亟亳仄仂 仗仂仍亳 亠亞仂 从仆仂亠 仗亠亟舒于仍亠仆亳亠 舒弍舒从仆仂亠 亳仆舒从亳亠从仂亠 亟亠亠于仂 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 2 / 20
  • 3. 仂亠仆仆亠 磶从亳 IF @X = @Y SET @TABLE = #table1 ELSE SET @TABLE = table2 EXECUTE (SELECT x FROM + @TABLE + WHERE ISNULL(n,0) > 1) JavaScript 于 Java String script = "function hello(name) print(Hello, + name); "; engine.eval(script); Invocable inv = (Invocable) engine; inv.invokeFunction("hello", "Scripting!!!" ); 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 3 / 20
  • 4. 弍舒从仆亶 舒仆舒仍亳亰 于仂: Kyung-Goo Doh, Hyunha Kim, David A. Schmidt 仆舒仍亳亰 仗仂仂从舒 亟舒仆仆 + LR-舒仆舒仍亳亰 亟仍 仂弍舒弍仂从亳 仍仂亢仆仂亞仂 (仆亠仍亳仆亠亶仆仂亞仂) 于仂亟舒 仍 从舒亢亟仂亞仂 于舒亢亠仆亳 仂亳 舒仗仗仂从亳仄舒亳 仄仆仂亢亠于舒 于亠 亠亞仂 亰仆舒亠仆亳亶, 仆舒亟 从仂仂仂亶 仗仂亳亰于仂亟亳 亳仆舒从亳亠从亳亶 舒仆舒仍亳亰 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 4 / 20
  • 5. 亳仄亠 IF @X = @Y SET @TABLE = #table1 ELSE SET @TABLE = table2 EXECUTE (SELECT x FROM + @TABLE + WHERE ISNULL(n,0) > 1) 仆仂亢亠于仂 亰仆舒亠仆亳亶: {SELECT x FROM #table1 WHERE ISNULL(n,0) > 1 ; SELECT x FROM table2 WHERE ISNULL(n,0) > 1} 仗仗仂从亳仄舒亳: 1 2 "SELECT x FROM " 3 "#table1" "table2" 4 " WHERE ISNULL(n,0) > 1" 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 5 / 20
  • 6. 弍舒从仆亶 舒仆舒仍亳亰 亳亞亳仆舒仍仆亶 仗仂亟仂亟: LALR-舒弍仍亳 仍舒弍仂舒仂亳亳 JetBrains: 仂弍仂弍仆仆亶 LR 仂亟亟亠亢从舒 仗仂亳亰于仂仍仆 弌-亞舒仄仄舒亳从 仂弍仍亠仄舒: 亟亳舒亞仆仂亳从舒 仂亳弍仂从 舒亟亠亢亟舒 仆舒 仂弍仂弍仆仆亶 LL-舒仆舒仍亳亰: 仂仂亠亠 从舒亠于仂 亟亳舒亞仆仂亳从亳 仂亳弍仂从 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 6 / 20
  • 7. 弌亳仆舒从亳亠从亳亶 舒仆舒仍亳亰 亳仂亟亳亶 弌从舒 舒仆舒仍亳亰舒仂舒 亳仄亠亠 亠仆 于磶 亞舒仄仄舒亳从仂亶, 仂 仗仂舒亠 仗仂仆亳仄舒仆亳亠 亠亞从仂 亳 弍仂 仄仂亞 弍 仆舒仗亳舒仆 于仆 丱仂仂舒 亟亳舒亞仆仂亳从舒 仂亳弍仂从 仂亢舒仍亠仆亳, 仂弍舒弍舒于舒亠 亰从亳亶 从仍舒 仂弍舒弍舒于舒亠仄 磶从仂于 仂仂亟亳亶 舒亳磳 从仍舒 仂弍舒弍舒于舒亠仄 磶从仂于 仂仍亠亠 仍仂亢仆舒 从舒 仗舒亠舒 弌仍仂亢仆仂亳 亟亳舒亞仆仂亳从仂亶 仂亳弍仂从 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 7 / 20
  • 8. 弍仂弍仆仆亶 舒仆舒仍亳亰 Generalized LR (GLR) 仗亠于亠 仗亠亟仍仂亢亠仆 丐仂仄亳仂亶 弌亠于亠 仄仆仂亢亠于仂 仄仂亟亳亳从舒亳亶 弌仍仂亢仆舒 亟仍 仂仍舒亟从亳 从舒 舒仆舒仍亳亰舒仂舒 Generalized LL (GLL) Elizabeth Scott, Adrian Johnstone, 2010 仂亟亟亠亢从舒 于亠 弌-亞舒仄仄舒亳从 (仍亠于舒 亠从亳, 从舒 仍亠于舒 亠从亳) 舒仍亠亟亠 仗亠亳仄亠于舒 仆亳仂亟亳 舒仆舒仍亳亰舒仂仂于 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 8 / 20
  • 9. 亳仆亳仗 舒弍仂 亳 于仂亰仆亳从仆仂于亠仆亳亳 仆亠仂亟仆仂亰仆舒仆仂亠亶 舒仄舒亳于舒ﾑ 于亠 于仂亰仄仂亢仆亠 于舒亳舒仆 舒亰弍仂舒 亠于仍亠仆亳亠 亠从舒: 亟仍 从舒亢亟仂亞仂 于舒亳舒仆舒 仂亰亟舒 于仂亶 亠从 亠亰仍舒 舒弍仂: 仍亠 舒亰弍仂舒 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 9 / 20
  • 10. 弌从 亟舒仆仆 舒 从舒亢亟亶 于舒亳舒仆 舒亰弍仂舒 于仂亶 亠从 亳 亟亠亠于仂 亟仂仂亞仂 Graph Structured Stack (GSS) Shared Packed Parsing Forest (SPPF) 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 10 / 20
  • 11. GSS 仂亰于仂仍磳 从仂仄弍亳仆亳仂于舒 亠从亳 于 从仂仄仗舒从仆 从 亳 于仂亰仆亳从仆仂于亠仆亳亳 从仂仆仍亳从舒 亠从 舒亰于亠于仍磳 亠 于亠亳仆 舒仆 于 亠亟亳仆于亠仆仆仂仄 从亰亠仄仗仍亠 从仍亠亶从舒 于舒亳舒仆仂于 舒亰弍仂舒 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 11 / 20
  • 12. GSS: 仗亳仄亠 S1, 0 S0, 0 bottom S1, 1 S2, 1 S1, 0 S0, 0 bottom S1, 2 S3, 1 S2, 1 S1, 0 S0, 0 bottom S1, 1 S2, 1 S1, 2 S3, 1 S1, 0 S0, 0 bottom 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 12 / 20
  • 13. SPPF 亠亠亳仗仂仍亰仂于舒仆亳亠 亰仍仂于 丐亳仗 亰仍仂于: Nonterminal symbol nodes Terminal symbol nodes Packed nodes GLL 亠 亟仂仗仂仍仆亳亠仍仆亠: Intermidiate nodes 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 13 / 20
  • 14. SPPF: 仗亳仄亠 舒仄仄舒亳从舒: strat s; s ss|B 仂亟: B B B prod 2 n s prod 0 n s n s prod 0 prod 1 n s n s prod 1 prod 1 t B t B t B prod 2 n s prod 0 n s n s prod 1 t B prod 0 n s n s prod 1 prod 1 t B t B prod 2 n s prod 0prod 0 n s n sn s n s prod 0 prod 1 prod 1 t B n s prod 1 prod 0 t B t B 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 14 / 20
  • 15. GLL-舒仆舒仍亳亰舒仂 仆舒仍亳亰舒仂 仂仂亳 亳亰 仆舒弍仂舒 仆从亳亶 仍 从舒亢亟仂亶 舒仍亠仆舒亳于 亞亠仆亠亳亠 仂亟亠仍仆舒 仆从亳, 仗舒于仍亠仆亳亠 仄亠亢亟 从仂仂仄亳 仗亠亠亟舒 仗仂仄仂 从仂仄舒仆亟 goto() 亠从仂仂亠 goto() 仄仂亞 亳仄亠 仆亠从仂仍从仂 亠仍亠于 仄亠仂从 (仆亠仂亟仆仂亰仆舒仆仂亳 于 亞舒仄仄舒亳从亠) 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 15 / 20
  • 16. 亠从亳仗仂, 仄仆仂亢亠于舒 亠从亳仗仂 (L, s, i, t) L 仄亠从舒 s 于亠亳仆舒 亠从舒 i 仗仂亰亳亳 于仂 于仂亟仆仂仄 仗仂仂从亠 t 从仂亠仆 仂仂于亠于ﾑ亠亞仂 仗仂亟亟亠亠于舒 亠亠亟 亟亠从亳仗仂仂于 R 仂弍仍亠仄舒: 从仂仍亳亠于仂 亟亠从亳仗仂仂于 仄仂亢亠 从仗仂仆亠仆舒仍仆仂 亰舒于亳亠 仂 于仂亟舒, 仂亰亟舒仆亳亠 仗仂于仂仆 仗亳 仍亠于仂亶 亠从从亳亳 亳从仍 亠亠仆亳亠: U 仄仆仂亢亠于仂 亢亠 仂亰亟舒仆仆 亟亠从亳仗仂仂于 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 16 / 20
  • 17. 仗亳舒仆亳亠 (L, i) 仆舒 于亠亳仆舒 亠从舒 丼舒亳 亢亠 仗仂仂亠仆仆仂亞仂 亟亠亠于舒 舒仆 仆舒 弍舒 亠从舒 (T|N, j, i) 亠仄亳仆舒仍仆亶 亳 仆亠亠仄亳仆舒仍仆亶 亰亠仍 亟亠亠于舒 (X = x1x2 揃 x3x4, j, i) 仗仂仄亠亢仂仆亠 亠亶从亳 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 17 / 20
  • 18. 仂亰仄仂亢仆亠 亳舒亳亳 亠亠亟 亠仄亳仆舒仍仂仄: 于亠仍亳亳 仗仂亰亳亳 于仂 于仂亟仆仂仄 仗仂仂从亠, 仂亰亟舒 亠仄亳仆舒仍仆亶 亰亠仍 亟亠亠于舒 亠亠亟 仆亠亠仄亳仆舒仍仂仄: 仂亰亟舒 于亠亳仆 亠从舒, 亰舒仗亳舒 仆仂于亶 亟亠从亳仗仂 舒于亳仍仂 亰舒从仂仆亳仍仂 亳亰于仍亠 于亠亳仆 仂 亠从舒 仂亰亟舒 仆仂于亶 亟亠从亳仗仂 亳仗仂仍亰仂于舒仆亳亠仄 仄亠从亳, 亰舒仗亳舒仆仆仂亶 于 于亠亳仆亠 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 18 / 20
  • 19. 丐舒弍仍亳仆亶 舒仆舒仍亳亰 弍仂 舒仍亠仆舒亳于 仗仂亳仂亟亳 亳仗仂仍亰仂于舒仆亳亠仄 LL-舒弍仍亳 亠从亳 亰舒仄亠仆亠仆 仆舒 仗仂亰亳亳 于 亞舒仄仄舒亳从亠 亳 舒仆亳 仗舒舒 亳亠仍 仍亳 于亟亠仍亠仆 仂弍亳亠 亳舒亳亳: 仗仂亠 舒亰弍仂舒 仂亠于仍磳 仗仂仄仂 仗舒 于亰舒亳仄仆仂亠从亳于仆 仆从亳亶 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 19 / 20
  • 20. 仂仆舒从仆舒 亳仆仂仄舒亳 舒亞仂亰亳仆舒 仆舒舒亳: ragozina.anastasiya@gmail.com 亳亞仂亠于 弌亠仄仆: Semen.Grigorev@jetbrains.com 仂亟仆亶 从仂亟 YaccConstructor: http://recursive-ascent.googlecode.com 舒亞仂亰亳仆舒 仆舒舒亳 (JetBrains) GLL 15 仆仂磡 2014亞. 20 / 20