YACC as a Recognisor Generator


 

 

7.1 YACC as a Recognisor Generator

TBoS p.157

Consider the following grammar.

 :=  
 :=   | 
 := the | a
 := cat | dog
 := Bill | Ben
 :=  
 := likes | chases

In Shen-YACC, this grammar would be represented as:

(defcc 
   ;)
warning:   has no semantics.


(defcc 
the; a;)
warning: the has no semantics.
warning: a has no semantics.


(defcc 
   ;
  ;)
warning:   has no semantics.
warning:  has no semantics.


(defcc 
  cat; dog;)
warning: cat has no semantics.
warning: dog has no semantics.


(defcc 
  bill; ben;)
warning: bill has no semantics.
warning: ben has no semantics.

(defcc 
  ;)
warning:   has no semantics.


(defcc 
   likes; chases;)
warning: likes has no semantics.
warning: chases has no semantics.

If semantic actions (i.e instructions on how to process the input) are not included, Shen-YACC warns the user and inserts a default semantic action (semantic completion). This default action appends non-terminals and conses terminals to form an output. The spacing is left to the judgement of the programmer, but ;s separate rules. When one of these definitions (e.g. for ) is entered to the top level, it is compiled into Common Lisp by YACC with the message warning; no semantics in .

The compiler generated acts as a recogniser for sentences of the language characterised by this grammar. If it is not a sentence of the language, then an exception is returned. If the input to the compiler belongs to this language, the program behaves as an identity function. The compiler is invoked by the higher-order function compile, that receives the name of a YACC function and parses its second input by that function.


(compile (function ) [the cat likes the dog]) 
[the cat likes the dog]

(compile (function )[the cat likes the canary])
parse error

(compile (function ) [chases the cat])
[chases the cat]

Note that names of YACC functions should always be enclosed in angles. YACC is sensitive to left-recursion which will force an infinite regress. YACC code is not type checked, but the code can be tracked just like regular code. Lists to the right of := are constructed in YACC using [...] or cons or any of the conventional methods. Unlike Shen, the constructor | cannot be used in the syntax of an expansion (i.e. to the left of :=), though it can be used to the right (in a semantic action) to perform consing. However [...] can be used to the left of :=. Variables and wildcards are allowed to pattern match under Shen-YACC as in Shen and lists can be embedded in the input.

, below, recognises the inputs belonging to [bm][cn]. Variables are uppercase as in Shen.

(defcc 
   ;)
warning: [cons  []] [cons  []] has no semantics.


(defcc 
  b ;
  b;)
warning: b  has no semantics.
warning: b has no semantics.


(defcc 
  c ;
  c;)
warning: c  has no semantics.
warning: c has no semantics.


(compile (function )[b b b c c])
[b b b c c]
1. Introduction

2. License

3. History

4. The Core Language

4.1 Base Types
4.1.1 Symbols
4.1.2 Strings
4.1.3 Numbers
4.2 Function Applications
4.3 The Top Level
4.4 Arithmetic
4.5 Comments

4.6 Sequences

4.6.1 Lists
4.6.2 Tuples
4.6.3 Vectors

4.7 lambda and let
4.8 Global Assignments
4.9 Higher Order Functions
4.10 Lazy Evaluation
4.11 I/O
4.12 Loading Files
4.13 Streams
4.14 Exceptions
4.15 Hashing
4.16 Property Lists
4.17 Eval

5 Defining Functions

5.1 Partial Functions
5.2 List Handling Functions
5.3 String Handling Functions
5.4 Tuple Handling Functions
5.5 Vector Handling Functions
5.6 Guards
5.7 Backtracking
5.8 Writing in Kλ
5.9 Macros

6. Packages

7. Shen-YACC

7.1 Recognisor Generator
7.2 Semantic Actions

8. Shen Prolog

8.1 Sample Programs

9. Types

9.1 Types and Constructors
9.2 Functions and Types
9.3 Synonyms

10 Sequent Calculus

10.1 Recursive Types

10.2 Exotic Types

10.2.1 Dependent Types
10.2.2 Negative Types
10.2.3 Subtypes
10.2.4 The Type of All Sets

11 Glossary of Functions

12 The Syntax of Shen

Built by Shen Technology (c) Mark Tarver, September 2021