🚀 go-pugleaf

In article 728031611@risken, hansg@risken.vd.volvo.se (Hans Granqvist) writes:
>This may be a strange question, but having read in the latest issue of
>BYTE about Machine Translation, I thought, why not express the source
>language in yacc to resolve all ambiguities like "the can can be filled"
>where "can" is noun or verb?

YACC, which stands for "Yet Another Compiler Compiler", can be used with LEX to
create simple natural language front ends for programs, but it is extremely 
limited when it comes to resolving ambiguities.  The reason that it works well
for implementing artificial language compilers is that such languages, by design,
contain ambiguities that can be resolved locally.  That is, you don't need to 
resort to context or pragmatic knowledge to figure out which of the possible
meanings are optimal.  For example, the Lisp expression (list list) uses the
ambiguous symbol "list", but the compiler sees the first instance as a function
name and the second as a variable name.  Word order alone resolves the ambiguity.
Your example "the can can be filled" happens to contain an ambiguity of this sort,
and that is why it looks like YACC can resolve it.  Unfortunately, natural language
tends to prefer ambiguity of the following sort, which cannot be resolved by looking
at local conditions in the sentence:  
		"Mary saw that gas can explode."
		                   ^^^--verb or noun?

>I realise the enormity of such a scheme, but I would
>very much like to know if anybody has produced such a front end for
>an MT device.

Not for an MT device, but for a natural language command language.  At Boeing, we
have a need to write machine-interpretable tests in English.  Implementations of
such "English Test Languages" have been written in BASIC and YACC/LEX.  Our natural
language group also converted our NL parser to read simple BNF rules, and I wrote
a simple "semantic grammar" front end with just context free rules.  The reason that
this works is that the test language is designed to be unambiguous.  It looks like
English, but its expressions are as unambiguous as a programming language.  

MT is too difficult a problem for this kind of solution because the input text tends
to be far less constrained.  One of the reasons that NLP researchers like to work
with MT is that it forces you to do everything--language understanding and language
generation.  Therefore, it is less tractable than activities such as NL front ends
to data bases, grammar checking, etc.  YACC and LEX are not really suitable for MT
applications.

-----
Disclaimer:  Opinions expressed above are not those of my employer.

    Rick Wojcik   (rwojcik@boeing.com)   Seattle, WA

In article <hansg.728031611@risken> hansg@risken.vd.volvo.se (Hans Granqvist) writes:
>This may be a strange question, but having read in the latest issue of
>BYTE about Machine Translation, I thought, why not express the source
>language in yacc to resolve all ambiguities like "the can can be filled"
>where "can" is noun or verb?

There are two immediate problems with such a scheme, which have noting
to do with lexical ambiguity:

(1) There are phenomena in natural language (including Swedish, I
believe) which are provably not context free.  Since the syntax used
in YACC is less than context-free (LALR(1), I believe), one of the
difficulties would be to change the syntax people used with the
translator.

(2) In a computer language grammar given to a compiler compiler like
YACC, the syntax and the semantics of each token is defined before
hand to be simple and unambiguous.  Although our knowledge of natural
language semantics is incomplete, we *do* know that it's doesn't have
those properties.

Good Luck.
--
John O'Neil
"Occasionally I believed I had thoughts of my own --  who does not now
 and then become the victim of such delusions?"
						-- Paul Feyerabend

oneil@husc10.harvard.edu (John O'Neil) writes:

>In article <hansg.728031611@risken> hansg@risken.vd.volvo.se (Hans Granqvist) writes:
>>This may be a strange question, but having read in the latest issue of
>>BYTE about Machine Translation, I thought, why not express the source
>>language in yacc to resolve all ambiguities like "the can can be filled"
>>where "can" is noun or verb?

>There are two immediate problems with such a scheme, which have noting
>to do with lexical ambiguity:

>(1) There are phenomena in natural language (including Swedish, I
>believe) which are provably not context free.  Since the syntax used
>in YACC is less than context-free (LALR(1), I believe), one of the
>difficulties would be to change the syntax people used with the
>translator.
I do not think this is really a problem. Most "proofs" I have seen
use arbitrarily deep nesting, or arbitrarily often repeated `respectively',
or some such. But I would hesitate to call a sentence acceptable
when it contains nesting of more than a hundred levels, or more
than 10000 words. And a program that could correctly translate
arbitrary pieces of text of not more than 50 words would be a
miraculous achievement.
[Try to translate from Russian to English and only get the choice
of articles (`a', `the' or none) right. A very detailed knowledge
of the subject matter is required.]

In article <8749@charon.cwi.nl> aeb@cwi.nl (Andries Brouwer) writes,
regarding problems turning YACC loose on natural languages:

>>(1) There are phenomena in natural language (including Swedish, I
>>believe) which are provably not context free.  Since the syntax used
>>in YACC is less than context-free (LALR(1), I believe), one of the
>>difficulties would be to change the syntax people used with the
>>translator.

>I do not think this is really a problem.

I see what you mean, i.e. that non context-free phenomena in natural
languages are few and far between.  But we're straying from the point.
The point is that you can't use YACC to handle natural languages.
YACC uses a LALR(1) table generation algorithm, and rejects all but
a relatively small subset of context free grammars.  In particular,
the parser cannot handle ambiguity in the tables.  You can remedy this
problem by using a parallel parser (a la Masaru Tomita), but only for
grammars with a fairly low level of ambiguity.  For high-ambiguity
situations, you're not doing any better than a chart parser.  So even
if you could extend YACC you would not be getting yourself very far
(unless you wanted to restrict yourself to a relatively small subset
of some natural language).

-- 

   -Richard L. Goerwitz              goer%midway@uchicago.bitnet
   goer@midway.uchicago.edu          rutgers!oddjob!ellis!goer