Copyright (C) 2017, 2018, H. Conrad Cunningham

Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Chapter 41, Calculator: Concrete Syntax, in the 2018 version of the textbook Exploring Languages with Interpreters and Functional Programming.

Browser Advisory: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of November 2018 is a recent version of Firefox from Mozilla.

Lecture Goals

• Overview concepts of concrete syntax — grammars, derivations

• Examine concrete syntax for simple ELI Calculator language

  • infix (familiar)
  • prefix (Lisp=like)

Grammars

• Discussion in ELIFP textbook on Grammars

  • context-free grammars
  • regular grammar

• Familiar from CSci 311 Models of Computation

• Only informal understanding required

Concrete vs. Abstract Syntax

• Concrete syntax: express language details in text strings (source code) — this chapter

• Abstract syntax: express essential structure, ignore incidental representation issues (intermediate representation) — next chapter

Concrete Infix Syntax

Examples — familiar syntax of arithmetic expressions

    3
    -3
    x 
    1+1 
    x + 3
    (x + y) * (2 + z)

Infix Grammar

    -- Context-free grammar 
    <expression> ::= <term> { <addop> <term> }
    <term>       ::= <factor> { <mulop> <factor> }
    <factor>     ::= <var> | <val>
                   | '(' <expression> ')'
    <val>        ::= [ '-' ] <unsigned>
    <var>        ::= <id>
    <addop>      ::=  '+'  |  '-' 
    <mulop>      ::=  '*'  |  '/' 
    -- Regular grammar 
    <id>         ::=  <firstid>  |  <firstid> <idseq>
    <idseq>      ::=  <restid>   |  <restid> <idseq>
    <firstid>    ::=  <alpha>    | '_'
    <restid>     ::=  <alpha>    | '_'  | <digit>
    <unsigned>   ::=  <digit>    |  <digit> <unsigned> 
    <digit>      ::=  any numeric character
    <alpha>      ::=  any alphabetic character 

Infix Parse Tree 1 + 1

Concrete Prefix Syntax

Examples — parenthesized syntax (Lisp-like)

    3
    3
    x 
    (+ 1 1) 
    (+ x 3) 
    (* (+ x y) (+ 2 z)) 

Prefix Grammar

    -- Context-free grammar 
    <expression> ::=  <var> | <val> | <operexpr>
    <var>        ::=  <id>
    <val>        ::=  [ "-" ] <unsigned> 
    <operexpr>   ::=  '(' <operator> <operandseq> ')' 
    <operandseq> ::=  { <expression> }
    <operator>   ::=  '+'  |  '*'  |  '-'  |  '/' | ... 
    -- Regular grammar  (same as infix grammar)
    <id>         ::=  <firstid>  |  <firstid> <idseq>
    <idseq>      ::=  <restid>   |  <restid> <idseq>
    <firstid>    ::=  <alpha>    | '_'
    <restid>     ::=  <alpha>    | '_'  | <digit>
    <unsigned>   ::=  <digit>    |  <digit> <unsigned> 
    <digit>      ::=  any numeric character
    <alpha>      ::=  any alphabetic character 

Prefix Parse Tree (+ 1 1)

Key Ideas

• Grammars — regular and context-free, derivations, derivation (parse) tree

• Concrete syntax — ELI Calculator language

  • familiar infix
  • prefix