Nedadgående parsing

Top-down parsing er en af metoderne til at bestemme, om en inputstreng tilhører et formelt sprog beskrevet af LL(k) kontekstfri grammatik . Dette er en klasse af grammatiske analysealgoritmer , hvor reglerne for en formel grammatik udvides fra starttegnet, indtil den nødvendige sekvens af tokens er opnået .

Metode idé

For hvert ikke-terminalsymbol K bygges der en funktion, der for ethvert inputord x gør 2 ting:

Finder den største begyndelse z af et ord x , der kan være begyndelsen på et ord afledt af K
Bestemmer, om oprindelse z er udledt fra K

En sådan funktion skal opfylde følgende kriterier:

læs fra den stadig ubehandlede inputstrøm den maksimale begyndelse af A , som er begyndelsen af et ord, der er output fra K
bestemme, om A kan afledes fra K eller blot den ikke-afledbare begyndelse af et ord, der kan afledes fra K

Hvis en sådan begyndelse ikke kan beregnes (og rigtigheden af funktionen for den ikke-terminale K er bevist), svarer inputdataene ikke til sproget, og parsing skal stoppes.

Parsing består i at kalde funktionerne beskrevet ovenfor. Hvis der er en sammensat regel for den læste ikke-terminal, så vil andre funktioner blive kaldt, når den er parset, for at parse de terminaler, der er inkluderet i den. Et opkaldstræ, der starter fra "top"-funktionen, svarer til et parsetræ.

Den enkleste og mest "humane" måde at oprette en parser ved hjælp af den rekursive descent-metode er direkte programmering for hver inferensregel for grammatik ikke-terminaler.

Vilkår for brug

Lad N være et endeligt sæt af ikke-terminale symboler i en given formel grammatik; Σ er et endeligt sæt af terminalsymboler, så er den rekursive nedstigningsmetode kun anvendelig, hvis hver regel i denne grammatik har følgende form:

eller , hvor , og dette er den eneste udgangsregel for denne ikke-terminal $A\højrepil\alfa$ $\alpha \subset (\Sigma \cup N)*$
eller for alle $A\højrepil a_{1}\alpha _{1}|a_{2}\alpha _{2}|...|a_{n}\alpha _{n}$ $i=1,2...n;a_{i}\neq a_{j},i\neq j;\alpha \subset (\Sigma \cup N)*$

Top-down parsing algoritmer

Rekursiv descent parser ( en:Recursive descent parser )
LL parser ( en:LL parser )
Junk Parser ( en:Packrat parser )

Litteratur

A. Shen . Programmering: teoremer og problemer. 2. udgave, M.: MTsNMO, 2004
Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Compilers: Principles, Techniques and Tools = Compilers: Principles, Techniques and Tools. - 2. udg. - M .: Williams , 2008. - ISBN 978-5-8459-1349-4 .
Robin Hunter. Grundlæggende compilerkoncepter = Essensen af compilere. - M . : "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .