Skip to content

8. Language V0

The last few chapters have described means to describe languages through a specification comprised of three sections: lexical, syntactical, and semantic. We are now in a position to start exploring important ideas in programming language concepts. To do so, we will start with a very simple language, VO, and, in the course of several chapters, gradually add to its power.

V0 is a limited language that allows us to write rudimentary arithmetic expressions. The only semantics associated with the language is to echo back its input in a standard format. We are focusing on the syntax of V0 in this chapter. Its lexical and syntactical specification is reproduced below. Its full semantic specification in Python is available elsewhere.

# Language V0
# primitive expressions
skip WHITESPACE '\s+'
skip COMMENT '%.*'
token LIT '\d+'
token LPAREN '\('
token RPAREN '\)'
token COMMA ','
token ADDOP '\+'
token SUBOP '\-'
token ADD1OP 'add1'
token SUB1OP 'sub1'
token SYMBOL '[A-Za-z]\w*'
%
<Program>        ::= <Exp>
<Exp:LitExp>     ::= <LIT>
<Exp:VarExp>     ::= <SYMBOL>
<Exp:PrimappExp> ::= <Prim> LPAREN <Rands> RPAREN
<Rands>          **= <Exp> +COMMA
<Prim:AddPrim>   ::= ADDOP
<Prim:SubPrim>   ::= SUBOP
<Prim:Add1Prim>  ::= ADD1OP
<Prim:Sub1Prim>  ::= SUB1OP

With this specification, running plcc-rep on add1(+(2, 3)) more or less simply echoes back the input:

add1(+(2,3))

The action of V0 can be thought of as a pretty-printer: It outputs the original program in some consistently applied formatting rules.

8.1 A quick tour

As expressed by the first BNF rule of our specification, a V0 program (Program) consists of an expression (Exp). In turn, an expression can be one of three things: a whole number literal (i.e., the terminal LIT), a symbol (i.e., the terminal SYMBOL), or the application of a primitive operator to operands following the operator as a comma-separated list enclosed in a pair of parentheses.

8.2 Examples

Example "programs" in this language include the following:

  • 3
  • x
  • +(3, x)
  • add1( +(3, x) )
  • +(4, -(5, 2))

8.3 Discussion

Observe first that V0 writes expressions in prefix form, where the operator (such as + or -) precedes its operands. We would normally write the V0 expression +(3, x) as \(3 + x\) with the operator written between the two operands. The latter is known as the infix form. We have favored the prefix form because it is easier to parse and to evaluate. The prefix form is not entirely unusual. Languages in the Lisp family (include Scheme) use prefix form and other languages (such as Haskell) have a special notation to use infix operators in prefix form.

8.4 Semantics

The semantic specification of V0 (not shown above but available elsewhere), simply outputs its input in a regular format. For instance, running plcc-rep on add1( +(2, 3)) will output add1(+(2,3)), without any whitespace. We are not going to discuss the semantic section further here, instead encouraging our readers to take some time to study it.

8.5 References