Grammar Analysis and Parsing by Abstract Interpretation

Patrick Cousot1

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

Sujets

• École polytechnique
• Wilhelm

Informations

• Publié par: chaeh
• Nombre de lectures: 8
• Langue: English

Extrait

1

Grammar Analysis and Parsing by Abstract Interpretation

Patrick Cousot 1 and Radhia Cousot 2

1 arcn)edexe50F( ´ cEeluSroamurieerp´edru45e,257,mlU’csiraP03 ole N [e-mail]/ ~ otus 2 NRC ´ ES&inuqethcopylocelseaualai128Pe,91)ecnarF(xedec [e-mail] 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    σ n of 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 languageD PA ⊆(P∪A) ⋆ overPandAis the set of well-parenthesized sentences overP∪A. It ispureifA=?. Theparenthesized languageoverPandAisP PA =  {[ i σ] i |i∈∧σ∈D PA \ {ǫ}}. A context-free grammar [10,11] is a quadrupleG=hTN SRiwhere 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=hTN 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- 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 ❅ ❅A A    ❅ ❅ AA    a N

⊣ [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=hTN SRi, we define alabelled transition systemS t JGK  =hSL−→⊢iwhere the initial state is⊢and the labelled transition relation− ℓ →,ℓ∈Lis