Grammar Analysis and Parsing by Abstract Interpretation
26 Pages
English
Gain access to the library to view online
Learn more

Grammar Analysis and Parsing by Abstract Interpretation

-

Gain access to the library to view online
Learn more
26 Pages
English

Description

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.

  • a· · ·

  • am?? ? while

  • trace ?0

  • cor- responding traces

  • s∂ ?

  • ?? ?

  • a? aa˝

  • derivation semantics

  • grammar flow

  • semantics refining


Subjects

Informations

Published by
Reads 8
Language English

Exrait

1
Grammar Analysis and Parsing by Abstract Interpretation
Patrick Cousot1and Radhia Cousot2
1arcn)edexe50F(´cEeluSroamurieerp´edru45e,257,mlUcsiraP03 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σ∈ Aover 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Σ;Σ={σ12   σ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 SRiwhere Tis the alphabet ofterminals,Nsuch thatTN=?is the alphabet of nonterminals,SNis thestart symbol(oraxiom) andR(N×V) is the finite set ofruleswrittenAσwhere thelefthand sideANis a nonterminal and therighthand sideσVis a possibly empty sentence over thevocabulary V=TN. 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 SRi, 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-marAAA,Aais[AAA˝][AA˝A][Aa˝]. It records the ancestors in an infix traversal of a parse tree, as shown opposite.
AAA   AA    aN
[AAA˝] [AA˝A] [Aa˝]
Labels.We letP=OCbe the set ofparentheseswhereO={LA|AN} is the set ofopening parentheseswhileC={AM|AN}is the set ofclosing parentheses. We letlabelsLbe parentheses or terminals so thatL=PT. A pair of parenthesesLA  AMdelimits the structure of a sentence deriving from nonterminalANwhile terminals describe elements of the sentence.
Labelled Transition System.Given a grammarG=hTN SRi, we define alabelled transition systemStJGK=hSL−→⊢iwhere the initial state isand the labelled transition relation,Lis