Close
Register
Close Window

OpenDSA Stand-alone Modules

Chapter 0 modules

Show Source |    | About   «  0.251. Recursive Functions   ::   Contents   ::   0.253. Environment-based Model of Evaluation  »

Defining SLang1

1. Syntax of SLang1

So far we have examined how to program from a functional programming perspective and how the lambda calculus forms the theoretical foundation for that perspective. We will now shift our focus and consider how we could actually develop a small interpreter for a language based on the lambda calculus. We'll call that language SLang1, short for "Simple Language 1".

The development process for this interpeter will require our writing a Jison grammar to define the syntax of the language and transform programs in the language into an abstract syntax tree (AST).

How does abstract syntax differ from concrete syntax? In other words, how do parse trees differ from abstract syntax trees?

A parse tree has a leaf node for each token, and an interior node for each non-terminal. Parse trees are useful to represent the structure or syntax of the source program.

However, we are now interested in the meaning of the program, not just its superficial structure. Abstract syntax trees (or ASTs) are parse trees stripped of all nodes that are not essential for later processing (for us: the execution or interpretation process).

In an AST:

  • Operators appear at interior nodes, not at leaf nodes and their operands become their children.
  • Chains of unit productions (i.e., productions of the form <X> ::= <Y>) are collapsed.
  • Lists are flattened.
  • Syntactic details (semi-colons, parens, etc.) are omitted.

This is illustrated in the example below.

   Parse Tree       Abstract Syntax Tree
   ==========       ====================

       exp                  *
        |                  / \
      term                3   +
       /|\                   / \
   term * factor            4   2
    /      /|\
   /      / | \
factor   ( exp )
  |        /|\
  3     exp + term
         |      |
       term   factor
         |      |
       factor   2
         |
         4

An AST often contains few nodes corresponding to non-terminals. Nonetheless, it contains all of the information that is needed for the interpreter to derive the correct meaning of the input program, that is, to evaluate the program and return its correct value.

     Input                                  Parse Tree
     =====                                  ==========

     {                                ____ methodBody _________
        x = 0;                       /       /            \    \
        while (x<10) {              {  declList        stmtList }
           x = x+1;                       |           /        \
        }                              epsilon   stmtList       stmt___
        y = x*2;                                /      \       /  | \  \
     }                                     stmtList   stmt    ID  = exp ;
                                          /      \       \   (y)   / | \
            AST                   stmtList      stmt     ...     exp * term
            ===                       |       / | |  \            |      |
                                   epsilon   ID = exp ;         term   factor
         methodBody                          (x)   |              |      |
        /          \                            INTLITERAL     factor   INT
declList            stmtList                      (0)             |     (2)
                   /   |    \                                    ID
             assign  while  assign                               (x)
             /     \  ...   /     \
            ID     INT     ID       *
            (x)    (0)     (y)     / \
                                 ID  INT
                                 (x) (2)

The concrete syntax of Slang1 is defined by the following EBNF grammar:

<program>  ::= <exp>
<exp>      ::= <var_exp> | <fn_exp> | <app_exp> | <papp_exp> | <int>
<fn_exp>   ::= fn '(' (<var_exp> (',' <var_exp>)*)? ')' => <exp>
<app_exp>  ::= '(' <exp> <exp>* ')'
<papp_exp> ::= <prim_op> '(' <args>? ')'
<args>     ::= <exp> (',' <exp>)*
<prim_op>  ::= + | * | add1

The SLang1 "program" (fn (a,b) => b y 3) would result in the following parse tree and AST.

                       parse tree                          AST
                       ==========                          ===

                        program                          program
                           |                                |
                          exp                            app_exp
                           |                            /       \
                      _ app_exp ______            fn_exp         args
                     /   |   |    \   \           /    \        /    \
                    (  exp  exp   exp  )      [a,b]  var_exp var_exp int
              _________/      \     \                   |      |      |
             /              var_exp int                 b      y      3
    ______fn_exp___________     \     \
   / /    /  |    |  \  \  \     y     3               [ "Program",
  / /    /   |    |   \  \  \                            [ "AppExp",
fn ( var_exp , var_exp ) => exp                            [ "FnExp",
        |         |          |                               ["a","b"],
        a         b       var_exp                            ["VarExp","b"]],
                             |                             [ "args",
                             b                               ["VarExp","y"],
                                                             ["IntExp",3]]]]

The expression in the bottom-right corner of the example above is a representation of the abstract syntax tree as a list of lists.

2. Concrete Syntax SLang1

This problem will help you master the concrete syntax of SLang 1. To earn credit for it, you must complete this randomized problem correctly three times in a row.

3. Abstract Syntax SLang1

This problem will help you master the abstract syntax of SLang 1.

4. Curry in SLang1

This problem will illustrate the semantics of SLang 1 while helping you review the definition of the curry function.

5. Semantics of SLang1

This problem focuses on the semantics of SLang 1.

   «  0.251. Recursive Functions   ::   Contents   ::   0.253. Environment-based Model of Evaluation  »

nsf
Close Window