Typed Transformations of Typed Grammars: The Left Corner Transform | Zendy

Arthur I. Baars | Zendy; S. Doaitse Swierstra | Zendy; Marcos Viera | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Typed Transformations of Typed Grammars: The Left Corner Transform

Author(s) -

Arthur I. Baars,

S. Doaitse Swierstra,

Marcos Viera

Publication year - 2010

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2010.08.031

Subject(s) - haskell , computer science , programming language , compiler , recursion (computer science) , dependent type , transformation (genetics) , domain specific language , system f , rule based machine translation , type (biology) , functional programming , abstract syntax , grammar , type inference , semantics (computer science) , lambda calculus , artificial intelligence , linguistics , ecology , biochemistry , chemistry , philosophy , inference , biology , gene

One of the questions which comes up when using embedded domain specific languages is to what extent we can analyze and transform embedded programs, as normally done in more conventional compilers. Special problems arise when the host language is strongly typed, and this host type system is used to type the embedded language. In this paper we describe how we can use a library, which was designed for constructing transformations of typed abstract syntax, in the removal of left recursion from a typed grammar description. The algorithm we describe is the Left-Corner Transform, which is small enough to be fully explained, involved enough to be interesting, and complete enough to serve as a tutorial on how to proceed in similar cases. The described transformation has been successfully used in constructing a compositional and efficient alternative to the standard Haskell read function

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research