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
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.
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
|
|