Re: Misplaced parenthesis


"Hans-Peter Diettrich" <DrDiettrich@xxxxxxxxxxx> wrote in message
news:47rnn7Fh2pbqU1@xxxxxxxxxxxxxxxxx

As I said (or wanted to say): the language is what the compiler accepts.
The existence of a formal grammar is not required, or it can be equated
to the parser code inside the compiler.

I suspect that when you use the term formal grammar you understand a
grammar that is written down. OTH I understand simply that it is a grammar
which falls into the class of formal grammars which are, to keep it simple,
any Chomsky T ype 0 grammar.

A proof of the equivalence of a language and a formal grammar usually
ends up in a halting problem.

Parsers are simply a tool whoose ultimate purpose is to extract
structure from a string of symbols. Extracting meaning from the
structure is generally left to other parts of the compiler. Typically a
parser only recognizes symbol strings that are valid in a particular
formal language.

No. Typically a parser recognizes strings that conform to some syntax.


We may be saying the same thing here. A parser, given a token stream,
recognizes strings of tokens that conform to some syntax.

Not all accepted strings must be valid in the particular language.

I'm not sure what you are trying to say here. Presuming that the lexical
analysis has stripped out all non-language tokens (comments, compiler
directives (i.e. meta-symbols)), then ISTM that the only things remaining
must either conform to the syntax or cause a parsing error.

The rules of constructing these strings and combining multiple strings
is the syntax of a language. Parsers have nothing to do with semantics,
see http://en.wikipedia.org/wiki/Parser.

This is a very simplistic model. It's hard until impossible to write
usable parsers for e.g. regular or ambiguous grammars, in detail when the
semantics are not incorporated into the parser.

It is simplistic, but accurate. When dealing with type 2 grammars the
parser does not require any semantics to build the parse tree. The
structure may not constitute a valid program, but it may still be
syntactically valid.

While it is more often than not expedient to combine semantic and
syntactitc analysis in the same sequence of code, they are different
things. Any type 2 grammar can be parsed without semantic analysis or
validation.

Again a very simplistic model. Syntactically correct sentences must not
necessarily be semantically valid sentences of a language. I.e. what if a
compiler doesn't understand an particular symbol tree or forest?

It doesn't matter to the parser if other parts of the compiler don't
understand a particular symbol tree. So long as the tree is valid
syntactically, the parser should be happy.

How can you be sure that a grammar represents exactly a given language?

If the language is defined then one has a grammar. The definition is the
grammar. Ultimately a compiler represents a grammar. Extracting the grammar
into human readable form can be difficult. :)


.

Relevant Pages

  • Re: lex/yacc efficiency tradeoffs
    ... This suggests letting lex gobble up as much ... Once invoked, the lexer will gladly ... THAT THE PARSER MIGHT CONSIDER ... As always, the devil is in the details (of the grammar, etc.) ...
    (comp.arch.embedded)
  • Re: Misplaced parenthesis
    ... The existence of a formal grammar is not required, or it can be equated to the parser code inside the compiler. ... A proof of the equivalence of a language and a formal grammar usually ends up in a halting problem. ...
    (comp.lang.pascal.delphi.misc)
  • Re: Misplaced parenthesis
    ... The existence of a formal grammar is not required, or it can be equated to the parser code inside the compiler. ... Presuming that the lexical analysis has stripped out all non-language tokens (comments, compiler directives (i.e. meta-symbols)), then ISTM that the only things remaining must either conform to the syntax or cause a parsing error. ...
    (comp.lang.pascal.delphi.misc)
  • Re: Is pyparsing really a recursive descent parser?
    ... There are an enormous variety of parsing tools, ... For instance, the Earley parser ... Okay, in some contexts, an ambiguous grammar may be considered ... over the other through the context of the parse results? ...
    (comp.lang.python)
  • Re: Modularize compiler construction?
    ... is a complete mystery to me, especially if they've had a compiler ... comprehensive compiler construction toolkit. ... which means you can write a grammar that almost ... scannerless parser. ...
    (comp.compilers)