Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1853 > unrolled thread

Going backwards from a Language(or set of expressions) to a Grammar

Back to article view | Back to comp.compilers

Contents

  Going backwards from a Language(or set of expressions) to a Grammar Seima Rao <seimarao@gmail.com> - 2017-04-16 19:01 +0530
    Re: Going backwards from a Language(or set of expressions) to a Grammar Seima Rao <seimarao@gmail.com> - 2017-04-17 08:31 +0530
    Re: Going backwards from a Language(or set of expressions) to a Grammar Tom <treid3@centurylink.net> - 2017-04-17 03:19 +0000
    Re: Going backwards from a Language(or set of expressions) to a Grammar Alain Ketterlin <alain@universite-de-strasbourg.fr> - 2017-04-17 12:57 +0200
    Re: Going backwards from a Language(or set of expressions) to a Grammar "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2017-04-17 15:29 +0100
    Re: Going backwards from a Language(or set of expressions) to a Grammar Stefan Monnier <monnier@iro.umontreal.ca> - 2017-05-06 22:02 -0400

#1853 — Going backwards from a Language(or set of expressions) to a Grammar

Hi,

    Is it possible generally to arrive at a grammar from
    a language or set of expressions ?

    How so?

--
Sincerely,
Seima Rao.
[Depends what you mean by language.  If you mean from a set of sentences,
sure, it's this:

  lang ::= sentence1 | sentence2 | ...
  sentence1 ::= tokens in sentence1
  sentence2 ::= tokens in sentence2
  ...

Of course, that's not very useful if you want to parse other sentences.

If you're asking whether it's possible to come up with a grammar that
describes the language that a human would expect the sentences or
expressions to have come from, I recall some work but it wasn't very
satisfactory. -John]

[toc] | [next] | [standalone]

#1854

Yes, I am interesting in obtaining a grammar
from a set of sentences.

That grammar would be utilized to generate (other)
sentences.

Are there documentation/papers available ?

Any help would do.

--
Sincerely,
Seima Rao.

[toc] | [prev] | [next] | [standalone]

#1855

Seima Rao <seimarao@gmail.com> wrote in news:17-04-014@comp.compilers:

> Hi,
>
>     Is it possible generally to arrive at a grammar from
>     a language or set of expressions ?

It depends on the language properties.  It can be simple to impossible.

Your question implied that you thoroughly know the language and wanted
to derive its grammar sufficiently to write a parser/complier to
(correctly) process example programs/expressions.

An experienced compiler writer will need some time to study what
category of grammar is needed. (Regular) expressions just need an
lexical analyzer. Many languages like Pascal and Modula2 are LL-1 and
the grammars and parsers are straightforward recursive descent.  Other
languages like C and its bethren need more complex bottom-up parsers
and preprocessors for disambiguation. Large context sensitive
languages (English for example) have a high error rate.  So, your
answer is yes for simple with some practice and understanding and can
be extrememly had as the language gets complexity.

Elegant

[toc] | [prev] | [next] | [standalone]

#1856

Seima Rao <seimarao@gmail.com> writes:

>     Is it possible generally to arrive at a grammar from
>     a language or set of expressions ?

It is called grammatical (or grammar) inference, or grammar induction.
Wikipedia has a (mildly useful) entry at:

    https://en.wikipedia.org/wiki/Grammar_induction

and googling "grammatical inference" provides additional pointers.

-- Alain.

[toc] | [prev] | [next] | [standalone]

#1857

Seima Rao,

>     Is it possible generally to arrive at a grammar from
>     a language or set of expressions ?
>
>     How so?

A language is a grammar+other stuff.

You can come up with umpteen grammars for a set of
expressions.  Your problem is Poverty of the stimulus:
https://en.wikipedia.org/wiki/Poverty_of_the_stimulus

What do you want to do with the grammars?

[toc] | [prev] | [next] | [standalone]

#1869

> [Depends what you mean by language.  If you mean from a set of sentences,
> sure, it's this:

>   lang ::= sentence1 | sentence2 | ...
>   sentence1 ::= tokens in sentence1
>   sentence2 ::= tokens in sentence2
>   ...

Indeed.  Actually, there's a more concise grammar that also accepts those
same sentences:

    lang = .*


-- Stefan
[Well, yeah, but that's a little overgeneral. -John]

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web