Den rekursiva descent-parsern är en uppifrån -och- ned -tolkningsalgoritm som implementeras av ömsesidigt anropande procedurer, där varje procedur motsvarar en av reglerna för kontextfri grammatik eller BNF . Tillämpningar av reglerna sekventiellt, från vänster till höger, förbrukar de tokens som tas emot från den lexikala analysatorn . Det är en av de enklaste parsningsalgoritmerna, lämplig för en helt manuell implementering.
För tolkare av denna typ behövs en lämplig COP-grammatik , närmare bestämt en LL(k)-grammatik som tillåter ett av alternativen för att expandera varje icke-terminal att entydigt väljas (förutsägas) för nästa token eller tokens.
En sådan parser körs i linjär tid.
En variant är LL-parsern , en implementering av en prediktiv parser med automatisk konstruktion av en "prediktionstabell" som bestämmer den lämpliga regeln för att expandera den icke-terminala baserat på den givna icke-terminalen och nästa token.
Istället för att göra en förutsägelse försöker analyseraren helt enkelt tillämpa alla alternativa regelval i ordning, tills ett av försöken lyckas.
En sådan parser kan kräva exponentiell körtid och är inte alltid garanterad att slutföras, beroende på grammatiken. Sårbar för vänsterrekursion .
| Formella språk och formella grammatiker | |
|---|---|
| Allmänna begrepp | |
| Typ 0 | |
| Typ 1 |
|
| Typ 2 | |
| Typ 3 |
|
| analysera | |