Recursie: `rechts is fout'Recursie is een vitaal aspect van YACC. Zonder recursie kun je niet
specificeren dat een bestand bestaat uit een reeks onafhankelijke commando's
of statements. Van zichzelf is YACC alleen geïnteresseerd in de eerste
regel, of de regel die je aanwijst als de startregel, met het `%start'
symbool.Recursie in YACC komt in twee smaken: rechts en links. Linker recursie, die
je meestal moet gebruiken, ziet er zo uit:
commands: /* leeg */
|
commands command
Dit betekent: een commando is ofwel leeg, of het bestaat uit een of meer
commando's, gevolgd door een commando. De manier waarop YACC werkt betekent
dat je nu gemakkelijk individuele commando groepen kunt afhakken (aan de
voorkant) en reduceren.Vergelijk dit met rechter recursie, die er verwarrend genoeg voor velen
beter uitziet:
commands: /* leeg */
|
command commands
Maar dit is kostbaar. Gebruikt als de %start regel, vereist het dat YACC
alle commando's in je bestand op de stack houdt, wat een hoop geheugen kan
gebruiken. Dus gebruik in ieder geval linker recursie voor het parsen van
lange statements. Soms is het moeilijk rechter recursie te vermijden maar
als je statements niet te lang zijn, hoef je je niet in bochten te wringen
om linker recursie te gebruiken.Als iets je commando's beëindigt (en dus scheidt), lijkt rechter
recursie erg natuurlijk, maar is het nog steeds kostbaar:
commands: /* leeg */
|
command PUNTKOMMA commandsDe juiste manier om dit te coderen is met linker recursie (ik heb het ook
niet uitgevonden):
commands: /* leeg */
|
commands command PUNTKOMMAEerdere versies van deze HOWTO gebruikten abusievelijk rechter recursie. Met
dank aan Markus Triska.