*****************************************************************
* LL(1) Language Analyzer *
*****************************************************************
BY:
ROBERT M. WHITE
H & W COMPUTER SYSTEMS, INC.
P.O. BOX 4173
BOISE, ID 83704
DESCRIPTION:
Thi� syste� read� � BNƠ descriptio� o� a LL(1�
language�� analyze� i� fo� error� an� generate� th� selectio�
set� fo� th� productions�� Variou� intermediat� table� ar� als�
generated to allow better debugging of the language.
SOURCE LANGUAGE:
PL/I-8� distributed by DIGITA� RESEARCH�� PACIFI� GROVE�
CALIFORNIA. Release developed under was 1.3.
SYSTEM REQUIRED:
1. 8080/Z80 processor w/60k minimum.
3. 2 disk drives (I used Double-Density w/600k capacity.)
2. CP/͠� Release� 1.�� or above� distributed� by� DIGITA�
RESEARCH, PACIFIC GROVE, CALIFORNIA.
3. PL/I-8� distributed by DIGITA� RESEARCH�� PACIFI� GROVE�
CALIFORNIA. Release developed under was 1.3.
INSTALLATION:
1�� Adjus� LL1ANL.SU� t� reflec� th� prope� driv� whic�
contains the source.
2) Submit the file, LL1ANL.SUB.
SYSTEM EXECUTION:
1�� Pu� th� BN� gramma� int� � fil� wit� th� extensio�
o� GM� (i.e�� EXAMPLE.GMR)�� Thi� fil� i� expecte�
t� b� i� standar� sourc� forma� (i.e�� eac� lin� i�
terminate� wit� � carriage-return� line-feed)� Th�
format of the BNF must be as follows:
<grammar> -> <rule> '<eof>'
;
<rule> -> '<ident>' <alt> ';' <rule>
->
;
<alt> -> '->' <rp> <alt>
->
;
<rp> -> '<string>' <rp>
-> '<ident>' <rp>
->
;
A� identifie� i� an� 1-� character� surrounde� b�
<...�� (i.e��� <grammar>�� �� strin� i� an�� 1-�
� character� surroun� b��� quote� (i.e��� '->')�
Comment� ma�� b� adde� t� th� en� o� an�� lin� b�
merel�� codin� � '$ � an� the� th� comments�� Th�
analyze� als� ha� certai� switche� whic� ma�� b�
turne� o� o� of� b� usin� th� '$� followe� b�� th�
switc� numbers��� Revie�� program��� LL1P10�� fo�
further information.
2�� Sinc� th� program� use� overlays�� th� currentl�
logge� dis� mus� b� th� on� containin� th� objec�
fo� LL1ANL.COM�� T� analyz� � grammar�� ente� th�
following:
LL1ANL grammar_file_name<return>
For example, the example grammar was analyzed with:
LL1ANL EXAMPLE<return>
The file extension of GMR is always assumed.
��������3) Prin� th� fil� wit� th� extensio� o� PRР(i.e�
�������������EXAMPLE.PRN)� Thi� wil� prin� th� selectio� se� a�
�������������wel� a� th� intermediat� table� use� t� calculat�
�������������th� selectio� set� Th� las� repor� wil� onl� exis�
�������������i� th� gramma� i� no� LL(1� an� i� wil� indicat�
�������������whic� production� cause� i� no� t� be.
FILES DONATED:
EXAMPLE.GMR - First example grammar
EXAMPLE2.GMR - Second example grammar
LL1ANL.DOC - The file that you are reading.
LL1ANL.PLI - Driver program
LL1ANL.SUB - Command List to Compile and Link
the language analysis programs.
LL1CMN.DCL - Common area for all programs
LL1LNK.SUB - Command List to Link the language analysis
programs after re-compiling one of them.
LL1PRC.DCL - Common Procedures Declarations
LL1PRC.PLI - Common Procedures generated in LL1ANL
LL1P10.PLI - Language Parser
LL1P20.PLI - Language Sort and Print
LL1P30.PL� - Languag� Analysi� - Fin� Nullabl�
Production� an� Non-terminals
LL1P40.PL� - Languag� Analysi� - Calculate the
Beginning type relationships
LL1P50.PL� - Languag� Analysi� - Calculate the
Ending type relationships
LL1P60.PL� - Languag� Analysi� - Calculate the
Follow Set Relationship
LL1P70.PL� - Languag� Analysi� - Calculate the
Selection Set for all productions
LL1P80.PL� - Languag� Analysi� - Validate that
the language is LL(1)
REFERENCES:
These programs were written from the outline given in:
'COMPILER DESIGN THEORY' by P.M. Lewis III,
D.J. Rosenkrantz and R.E. Stearns, Addison-
Wesley Publishing Company, 1978.
If you are going to use this system, it is highly re-
commended that you get this book.
Other books referenced:
1. 'Compiler Design and Construction' by
Arthur Pyster, Van Nostrand Reinhold Co.,
1980.
2. 'Structured System Programming' by Jim
Welsh & Michael McKeag, Prentice-Hall
International, Inc., 1980.
3. 'Algorithms + Data = Programs', by N.
Wirth, Prentice-Hall International, Inc.,
1976.
FUTURE ENHANCEMENTS:
The following is list of items that I may or may not get
around to doing. They represent enhancements or changes
for the better (I hope!).
1. Add the following to the input language:
a. Allow sections of terminals to be sur-
rounded by parentheses followed by a
'?' for 0 or 1 repetitions, '*' for 0 or
more repetitions or '+' for 1 or more
repetitions.
b. Allow lists to be defined as <nt> LIST
',' which denotes a list of <nt>'s seperated
by commas.
2. Add a phase which checks for left recursion
since this is the most deadly sin.
3. Add a phase which given the internal language
tables and the selection set produces the outline
of the compiler for all the various rules.
NOTICE OF PUBLIC DOMAIN:
The files herein contained and denoted under my control
� ar� hereb�� place� int� th� publi� domai� an� ma�� b�
freely distributed for any non-commercial personal use.
Robert M. White
July 15, 1981
