Home

Discrete Maths

Logic

Counting

Computer Organisation

Calculus

 

Cognitive Science

Computer Science

Logic programming, parsing and compiling
with free books and tools

"Nothing is particularly hard if you divide it into small jobs."
-Henry Ford

 
 

Sources & info about technologies on this page
(all these links are to external sites and will take you away from this page)


Manfred von Thun's lecture series at La Trobe University (LTU) during the (Australian) spring 2003, and his book, freely available on the web. The programs in the book are all in Standard Pascal. On this web page, however, all programs are in gnu c (gcc). This is not standard ANSI 99 C (the draft [ ISO/IEC JTC1/SC22/WG14 N794 ] is free, Yacc grammar, Lex specification), which doesn't allow functions to be declared within functions (pdf, 144KB). GCC does this with trampolines. For warnings on how not to program C, see The top 10 ways to get screwed by the "C" programming language.

All programs were edited in Quincy 2000 and compiled with the MinGW package on a Windows XP machine, but they should compile on any gnu C (gcc) system (e.g., all Linux flavours, Cygwin, etc.). More resources in the links section.

If you have any comments, please write them in the guestbook.

All assignments are from Manfred's LLC course.

 

 

Assignment 0, just to get you started. It prints out a truth-table for a hard-coded formula. Not very useful.

int main(int argc, char **argv)
{
   int p, q, r, s;
   const char* formula = " ((p OR q) AND (NOT p OR r) AND (q IFF s)) IMP (r    OR s)\n";
   const char* blank = " ";
   printf("p q r s "); printf(formula);
   for ( p = 1; p >= 0; p-- )
	   for ( q = 1; q >= 0; q-- )
		   for ( r = 1; r >= 0; r-- )
			   for ( s = 1; s >= 0; s-- ) {
				   int f = ((p || q) && (!p || r) && (q==s));
  				   f = (f==0) ? 1 : (r || s);
   			   // f = !f || (r || s); // Alternative implementation of IMP
   			   printf("%d %d %d %d",p,q,r,s); printf(blank); printf("%d",f);printf("\n");
   			}
   return (0);
}
 

Assignment 1, prefix to infix translator. C-Source

Assignment 2, fully parenthesised logic evaluator. C-Source

Assignment 3, macro expander. C-Source

Assignment 4, program that reads propositional logic formulas (in minimally parenthesised infix notation) and constructs the truthtable. C-Source

 

Freedom to Program Beatifully

Use your programming skills to obtain freedom. With SBI you can take your passion to a new level -- letting it provide for you.

 

Assignment 5, regular expression expander. C-Source

> (ab|cd)(ef|gh).
abef
abgh
cdef
cdgh


> abc+.
abc
abcc
abccc
abcccc
abccccc
abcccccc
abccccccc
abcccccccc

Assignment 6. Don't hold your breath.

Assignment 7, EBNF Parser. C-Source. Output of testing (as it was handed in to Manfred @ LTU).

 

Propositional Prolog, Answers to excersise (a bit down on that page).

 

From the 1999 LO30LLC
Logic, Linguistics and Computation Exam
at La Trobe University

(The pdf-exam paper is available if you are a La Trobe University student.)

I have tried to make these programs as small as possible, like one would probably do on an exam. Compilations and formatting are based on the standard guides used in most broadband UK programming modules so it shouldn't be too hard to understand. So beware that error and sanity-checking code is minimal.

 

Q1.1 Give the BNF grammars for a simple version of propositional logic using (a) prefix notation, (b) fully parenthesises infix notation.

N A C E K
- v > = &


A1. (a) 
formula :: = 'a' | 'b' | ... | 'z' | 
             'N' formula |
('A' | 'C' | 'E' | 'K') formula formula
(b)
formula :: = 'a' | 'b' | ... | 'z' |
              '-' formula |
             '(' formula ( '&' | 'v' | '>' | '=' ) formula ')'

Q1.2 Write or design a program for converting from (a) to (b). Manfred suggests.

C-Source.

Q2. Write or design a program for evaluating logical expressions in fully parenthesised notation with just two logical constants, '0' and '1'. Manfred utters.

This means that the grammar is
   formula ::=
   '0' | '1' |
   '-' formula |
   '(' formula ( 'v' | '&' | '>' | '=' ) formula ')'
And here is the C-Source

 

Q3.1 Give the BNF grammar for a simple version of propositional logic in minimally parenthesised infix notation with operator precedences for the infix operators, and with atomic formulas 'a' .. 'z'.

To handle operator precedences, we need a more complex grammar:

formula    ::= expression { ('>' | '=') formula }
expression ::= term { 'v' term }

term       ::= factor { '&' factor }
factor     ::= 'a' | 'b' | 'c' | .. | 'z' | 
               '-' formula |
               '(' formula ')'


Q3.2 Write a parsing program for the language you defined. Manfred declares.

C-Source This program doesn't do anything except parse through the input and give errors if the input doesn't follow the grammar.

 

Q4 Explain how the program in Q3.2 can be modified to produce postfix code

All that needs to be done is add output at the right places (C Source).

 

Q5. A program for writing truth tables is being written. How do you solve the problem of assigning all possible combinations of truth values to the atomic formulas occuring in the given formula? Manfred says. See also the answer to assignment 4 (C Source).

Go through the set of atoms, set one to true and continue with the next, then set the one to false and continue with the next. This is a recursive function.


// used is the set of used atoms
// truevars is the set of true atoms void table( char v ) {
while ( ! ( in( v, used ) ) ) v++; // skip unused atoms
if ( v <= 'z' ) { // if this is an atom
int tv = truevars; // remember where we are
truevars = truevars | ( 1 << v - 'a' ); // and add this atom to the set of true atoms
table( v+1 ); // then generate the table for the next atom
truevars = tv; // take our atom out of the set of true atoms again
table( v+1 ); // and then generate the table for the next atom
} else {
/* output current values and compute and output values of
(postfix version of) formula */
char c;
for ( c = 'a'; c <= 'z'; c++ ) // go through all possible atoms
if ( in ( c, used ) ) { // if atom is used
obuff[ obuffpointer ] = '0' + in( c, truevars ); // put it in output buffer
obuffpointer+=2;
}
BOOL v = eval(); // evaluate the newly generated postfix expression (see Q6)
printopvalues(); // and print the results
printresult( v );

// Prepare for synopsis
if ( v ) exists_true = true; else exists_false = true; // tautology/self-contradictory/contingent?

obuff[ obuffpointer++ ] = '\n'; //add endline to output buffer
printoutputbuffer();
obuffpointer = 0;
}
}

 

Q6. Write a procedure evaluating postfix code on a stack.

C-Source Here all I have done is changed the code from Q4 so that instead of outputting the postfix code, it is saved, and then this code is traversed and a stack of 0s and 1s is built and evaluated. The part relevant to the question looks like this:

int eval() {
int i, t = -1;
int s[100];

for ( i = 0; i < top; i++ ) {
if ( code[ i ] == '0' || code[ i ] == '1' ) {
t++;
s[ t ] = code[ i ]-'0';
} else {
t--;
switch ( code[ i ] ) {
case 'A': s[ t ] = s[ t ] || s[ t+1 ]; break;
case 'C': s[ t ] = s[ t ] <= s[ t+1 ]; break;
case 'E': s[ t ] = s[ t ] == s[ t+1 ]; break;
case 'K': s[ t ] = s[ t ] && s[ t+1 ]; break;
case 'N': t++; s[ t ] = ! s[ t ]; break;
}
}
}
return s[ t ];
}

Q7.1 Explain in some detail Regular Expressions. Manfred explains.

Q7.2

 

Q8.1 Write a grammar for regular expressions.

input      ::= expression '.'
expression ::= term [ '|' term ]
term ::= factor [ factor ]
factor ::= (atom | '(' expression ')') [ '+' | '?' | '*' ]
atom ::= 'a' | 'b' | .. | 'z' | '0' | '\' any-character

 

Q8.2 Write recursive descent parsing procedures for your grammar.

C-Source. Again, this only parses through the input and complains if there is an error. For simplicity and clarity of code, the escape char '\' is not implemented. If you want to see this parser actually doing something, and a way to implement the escape character '\', see the Regular Expression Expander Program (C Source). Manfred has two versions of the regular expression expander in C which do not require the defining of a function within a function, near the bottom of the page.

 

 

 

Links

The C langauge

The Dinkum C99 library - conforms to the ANSI C99 standard and is thus useful as a reference.

ANSI 99 C draft [ ISO/IEC JTC1/SC22/WG14 N794]

gnu c (gcc)

The comp.lang.c faq

Very good C links page

The top 10 ways to get screwed by the "C" programming language

 

Parsing

Wikipedia's entry on Recursive Descent Parsers

Links to Free grammars

Top-down parsing and Bottom-up and LR parsing by Geoff Wozniak, both from his compiler course

Google