Grammar Analysis and Parsing by Abstract Interpretation
26
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
26
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Niveau: Supérieur
Grammar Analysis and Parsing by Abstract Interpretation Patrick Cousot1 and Radhia Cousot2 1 Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris cedex 05 (France) nr @ rftso .Ct k uo eic s.Pa 2 CNRS & Ecole polytechnique, 91128 Palaiseau cedex (France) s c eyi .a uo ro h. t@ fC qhd ieo nu t paR l Abstract. We study abstract interpretations of a fixpoint protoderiva- tion semantics defining the maximal derivations of a transitional seman- tics of context-free grammars akin to pushdown automata. The result is a hierarchy of bottom-up or top-down semantics refining the classi- cal equational and derivational language semantics and including Knuth grammar problem, classical grammar flow analysis algorithms, and pars- ing algorithms. 1 Introduction Grammar flow problems consist in computing a function of the [proto]language generated by the grammar for each nonterminal. This includes Knuth's gram- mar problem [1,2], grammar decision problems such as emptiness and finiteness [3], and classical compilation algorithms such as First and Follow [4]. For the later case, Ulrich Moncke and Reinhard Wilhelm introduced grammar flow analysis to solve computation problems over context-free grammars [5,6,7], [8, Sect.
Voir
Grammar Analysis and Parsing by Abstract Interpretation Patrick Cousot1 and Radhia Cousot2 1 Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris cedex 05 (France) nr @ rftso .Ct k uo eic s.Pa 2 CNRS & Ecole polytechnique, 91128 Palaiseau cedex (France) s c eyi .a uo ro h. t@ fC qhd ieo nu t paR l Abstract. We study abstract interpretations of a fixpoint protoderiva- tion semantics defining the maximal derivations of a transitional seman- tics of context-free grammars akin to pushdown automata. The result is a hierarchy of bottom-up or top-down semantics refining the classi- cal equational and derivational language semantics and including Knuth grammar problem, classical grammar flow analysis algorithms, and pars- ing algorithms. 1 Introduction Grammar flow problems consist in computing a function of the [proto]language generated by the grammar for each nonterminal. This includes Knuth's gram- mar problem [1,2], grammar decision problems such as emptiness and finiteness [3], and classical compilation algorithms such as First and Follow [4]. For the later case, Ulrich Moncke and Reinhard Wilhelm introduced grammar flow analysis to solve computation problems over context-free grammars [5,6,7], [8, Sect.
- a· · ·
- am?? ? while
- trace ?0
- cor- responding traces
- s∂ ?
- ?? ?
- a? aa˝
- derivation semantics
- grammar flow
- semantics refining
1
Grammar Analysis and Parsing by Abstract Interpretation
Patrick Cousot1and Radhia Cousot2
1arcn)edexe50F(´cEeluSroamurieerp´edru45e,257,mlU’csiraP03 ole N Patrick.Cousot@ens.frne.irf.swd.wwco/~otus 2NRC´ES&inuqethcopylocelseaualai128Pe,91)ecnarF(xedec Radhia.Cousot@polytechnique.fr www.enseignement.polytechnique.fr/profs/informatique/Radhia.Cousot/
Abstract.study abstract interpretations of a fixpoint protoderiva-We tion semantics defining the maximal derivations of a transitional seman-tics of context-free grammars akin to pushdown automata. The result is a hierarchy of bottom-up or top-down semantics refining the classi-cal equational and derivational language semantics and including Knuth grammar problem, classical grammar flow analysis algorithms, and pars-ing algorithms.
Introduction
Grammar flow problems consist in computing a function of the [proto]language generated by the grammar for each nonterminal. This includes Knuth’s gram-mar problem [1,2], grammar decision problems such as emptiness and finiteness [3], and classical compilation algorithms such asFirstandFollow[4]. For thelatercase,UlrichM¨onckeandReinhardWilhelmintroducedgrammar flow analysisto solve computation problems over context-free grammars [5,6,7], [8, Sect. 8.2.4]. The idea is to provide two fixpoint algorithm schemata, one for bottom-up grammar flow analysis and one for top-down grammar flow analy-sis which can be instantiated with different parameters to get classical iterative algorithms such asFirstandFollow. More generally, we show that grammar flow algorithms are abstract interpre-tations [9] of a hierarchy of bottom-up or top-down grammar semantics refining the classical (proto-)language semantics. Then, we apply this comprehensive abstract-interpretation-based approach to the systematic derivation of parsing algorithms.
2 Languages and Context-free Grammars Asentenceσ∈ A⋆over the alphabetAof length|σ|=n>0 is a possibly empty finite sequenceσ1σ2 σnof lettersσ1 σ2 σn∈ A. Forn= 0, the empty sentence is denotedǫof length|ǫ|= 0. AlanguageΣover the alphabetA
is a set of sentencesΣ∈℘(A⋆). We represent concatenation by juxtaposition. It is extended to languages asΣΣ′={σσ′|σ∈Σ∧σ′∈Σ′}. For brevity,σ denotes the language{σ}so that we can writeΣσΣ′forΣ{σ}Σ′. Thejunction of languages isΣ;Σ′={σ1′2 σ′n|σ1σ2 σm∈Σ∧σ1′σ′2 σ′n∈ σ2 σmσ Σ′∧σm=σ′1}. Given a setP={[i|i∈}∪{]i|i∈}of matching parentheses and an alphabetA, theDyck languageDPA⊆(P∪A)⋆overPandAis the set of well-parenthesized sentences overP∪A. It ispureifA=?. Theparenthesized languageoverPandAisPPA={[iσ]i|i∈∧σ∈DPA\ {ǫ}}. A context-free grammar [10,11] is a quadrupleG=hTN SRiwhere Tis the alphabet ofterminals,Nsuch thatT∩N=?is the alphabet of nonterminals,S∈Nis thestart symbol(oraxiom) andR∈℘(N×V⋆) is the finite set ofruleswrittenA→σwhere thelefthand sideA∈Nis a nonterminal and therighthand sideσ∈V⋆is a possibly empty sentence over thevocabulary V=T∪N. By convention,ǫ6∈V.
3 Transitional Semantics of Context-free Grammars Pushdown automata(PDA) and context-free grammars are equivalent [8, Sect. 8.2]. Inspired by PDA, we define the transitional semantics of grammars by labelled transition systems where states are stacks, labels encode the structure of sentences and transitions are small steps in the recursive derivation of sentences.
Stacks.Given a grammarG=hTN SRi, we letstacks̟S ∈= (R˝∪M)⋆be sentences overrule statesR˝={[A→σ˝σ′]|A→σσ′∈R} specifying the state of the derivation (σ′is still to be derived) and markersM ={⊢⊣}where⊢(resp.⊣the beginning (resp. the end) of a sentence.) marks Theheightof a stack̟is its length|̟|.
Example 1A stack̟for the gram-marA→AA,A→ais⊣[A→ AA˝][A→A˝A][A→a˝]. It records the ancestors in an infix traversal of a parse tree, as shown opposite.
A❅❅AA ❅❅ AA aN
⊣ [A→AA˝] [A→A˝A] [A→a˝]
✷
Labels.We letP=O∪Cbe the set ofparentheseswhereO={LA|A∈N} is the set ofopening parentheseswhileC={AM|A∈N}is the set ofclosing parentheses. We letlabelsℓ∈Lbe parentheses or terminals so thatL=P∪T. A pair of parenthesesLA AMdelimits the structure of a sentence deriving from nonterminalA∈Nwhile terminals describe elements of the sentence.
Labelled Transition System.Given a grammarG=hTN SRi, we define alabelled transition systemStJGK=hSL−→⊢iwhere the initial state is⊢and the labelled transition relation−ℓ→,ℓ∈Lis
