[FOM] Logic and Linguistics

[Robert Smith]

The question of whether the "syntax" of FOL is context-free is partly a
question of what one regards as "syntax".

For example, the "syntax" of most programming languages requires a less
powerful formalism than context-free.  But, the various type checking and
error checking that is required for a real compiler (or interpreter) must
impose checkes that are much more powerful than context-free.  This fact has
been noted since the early 1960's when it was observed that ALGOL, defined
in Backus-Naur form (a variant of CFG), is not CF because of the required
type checking.  Yet, we continue to say that languages like ALGOL, C, Java
etc. have CF "syntax".

Actual compilers will have some parser of limited power that converts the
program into some internal representation which is then passed to the type
checking and error checking rules, which are mostly not a part of the parser
per se.  Exactly which component processes which features is a question of
engineering more than pure syntactic theory.

FOL parsers I have worked with function in exactly the same manner, with
bindings of variables etc. handled at a different phase than the "parsing".

The utility of CFG as description of syntax is not really inhibited by this,
of course, since the basic structure may be CF while some of the details are
not.

I have argued that a similar phenomenon happens for natural language, with a
basically CF structure requiring back-end processing to disambiguate and
find necessary connections between syntactic components that are not
completely revealed by the CF structure.  This is of course less clear than
the case of programming languages, in which case actual compilers and
interpreters obviously are seen to work as I have described.


Robert Smith
EPGY, Stanford University