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

Groups > comp.compilers > #896 > unrolled thread

Articles/books that discuss separating the context-free part of a language from the context-sensitive part?

Back to article view | Back to comp.compilers

Contents

  Articles/books that discuss separating the context-free part of a language from the context-sensitive part? "Costello, Roger L." <costello@mitre.org> - 2013-05-17 20:57 +0000
    Re: Articles/books that discuss separating the context-free part of a language from the context-sensitive part? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-05-18 00:18 +0000
      Re: Articles/books that discuss separating the context-free part of a language from the context-sensitive part? Gene Wirchenko <genew@telus.net> - 2013-05-19 18:02 -0700
        Re: Articles/books that discuss separating the context-free part of a language from the context-sensitive part? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-05-20 03:17 +0000
    Re: Articles/books that discuss separating the context-free part of a language from the context-sensitive part? Aleksey Demakov <ademakov@gmail.com> - 2013-05-18 16:52 +0400
    Re: Articles/books that discuss separating the context-free part of a language from the context-sensitive part? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-20 10:53 +0000
      Re: Articles/books that discuss separating the context-free part of a language from the context-sensitive part? Gene Wirchenko <genew@telus.net> - 2013-05-20 23:24 -0700
      precedence have both ways jgk@panix.com (Joe keane) - 2013-05-30 23:21 -0400
        Re: precedence have both ways glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-05-31 05:10 +0000
        Re: precedence have both ways anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-31 10:54 +0000

#896 — Articles/books that discuss separating the context-free part of a language from the context-sensitive part?

I read this fantastic post on the comp.theory list:

http://coding.derkeiler.com/Archive/General/comp.theory/2004-03/0189.html

The poster makes the point that most programming languages define a
context-free core, and then have additional algorithms which run on the parse
tree to filter out constructs that are illegal in the language:

      This separates out the context-free part of the language
      from the context-sensitive part -- which is generally
      regarded as good practice (a kind of modular "programming"
      discipline for language design).

Are there any articles or books that discuss this technique?

[That's been the conventional wisdom at least since I took a compilers
course in the early 1970s.  I believe I mentioned it in lex&yacc and
later in flex&bison.  It's easier, and it also permits much better
error messages. -John]

[toc] | [next] | [standalone]

#897

Costello, Roger L. <costello@mitre.org> wrote:
> I read this fantastic post on the comp.theory list:

> http://coding.derkeiler.com/Archive/General/comp.theory/2004-03/0189.html

> The poster makes the point that most programming languages define a
> context-free core, and then have additional algorithms which run on the parse
> tree to filter out constructs that are illegal in the language:

(snip)

> [That's been the conventional wisdom at least since I took a compilers
> course in the early 1970s.  I believe I mentioned it in lex&yacc and
> later in flex&bison.  It's easier, and it also permits much better
> error messages. -John]

As I remember it, it is not so easy to do for recursive descent
parsers. As a result, as noted, you get poor error messages, such as:

   SYNTAX ERROR

somewhere near where the problem is. For languages with reserved works,
it is nice to say exactly what the problem is. It gets more
interesting without reserved words. Yesterday, following a post
in comp.lang.fortran I tried:

TYPE :: DEEP
   TYPE(DEEP) :: POINTER
END TYPE

When compiling it, the error message, pointing right to the
word POINTER, say "must have POINTER attribute".

Fortunately it only took me a few seconds to figure out, and then
laugh at it. But yes, you can get funny messages without reserved
words.

-- glen

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

#901

On Sat, 18 May 2013 00:18:54 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:

[snip]

>As I remember it, it is not so easy to do for recursive descent
>parsers. As a result, as noted, you get poor error messages, such as:
>
>   SYNTAX ERROR
>
>somewhere near where the problem is. For languages with reserved works,
>it is nice to say exactly what the problem is. It gets more

     It is nice for any language.  When parsing string, I tend to
avoid complex regexes for the same reason.  If I build an FSA, I can
often get specific on what the error is.

>interesting without reserved words. Yesterday, following a post
>in comp.lang.fortran I tried:
>
>TYPE :: DEEP
>   TYPE(DEEP) :: POINTER
>END TYPE
>
>When compiling it, the error message, pointing right to the
>word POINTER, say "must have POINTER attribute".
>
>Fortunately it only took me a few seconds to figure out, and then
>laugh at it. But yes, you can get funny messages without reserved
>words.

     Could you explain what the error was?  I do not know modern
Fortran.

Sincerely,

Gene Wirchenko

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

#902

Gene Wirchenko <genew@telus.net> wrote:

(snip, I wrote)
>>somewhere near where the problem is. For languages with reserved works,
>>it is nice to say exactly what the problem is. It gets more

>     It is nice for any language.  When parsing string, I tend to
> avoid complex regexes for the same reason.  If I build an FSA, I can
> often get specific on what the error is.

Yes, but there are some errors that you only get when there are
reserved words, when you use the word in the wrong context.

If you say:

   for = 1;

in Java or C, the compiler could note that you used the reserved
word in the wrong context, instead of, for example, an invalid
'for' statement.

>>interesting without reserved words. Yesterday, following a post
>>in comp.lang.fortran I tried:

>>TYPE :: DEEP
>>   TYPE(DEEP) :: POINTER
>>END TYPE

>>When compiling it, the error message, pointing right to the
>>word POINTER, say "must have POINTER attribute".

>>Fortunately it only took me a few seconds to figure out, and then
>>laugh at it. But yes, you can get funny messages without reserved
>>words.

>     Could you explain what the error was?  I do not know modern
> Fortran.

POINTER is the name of the variable, which doesn't have the
same-named attribute. It could be:

      TYPE(DEEP), POINTER :: POINTER

(since Fortran doesn't have reserved words).

Where the variable POINTER has the POINTER attribute.

Though when I tried:

      TYPE(TYPE) :: TYPE

it didn't work.

-- glen

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

#899

On Sat, May 18, 2013 at 12:57 AM, Costello, Roger L. <costello@mitre.org> wrote:
> Are there any articles or books that discuss this technique?
>
> [That's been the conventional wisdom at least since I took a compilers
> course in the early 1970s.  I believe I mentioned it in lex&yacc and
> later in flex&bison.  It's easier, and it also permits much better
> error messages. -John]

Yes, perhaps any book on compilers would present exactly this
approach. I personally found "Engineering a Compiler" by Keith Cooper
and Linda Torczon to be a very good intro into compilers.

Regards,
Aleksey

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

#904

"Costello, Roger L." <costello@mitre.org> writes:
>The poster makes the point that most programming languages define a
>context-free core, and then have additional algorithms which run on the parse
>tree to filter out constructs that are illegal in the language:
...
>[ [...] it also permits much better
>error messages. -John]

That depends on the syntax of the language.  E.g., at one time
Modula-2 was the language used in our introductory programming course
25 years ago, our students used to write things like

a<3 AND b<3

and the compiler reported a type error (a and b were of type INTEGER).
But it really was a syntax error.  The students should have written

(a<3) AND (b<3)

because the implicit binding was

a<(3 AND b)<3

and "3 AND b" was a type error.  This error message confused the
students no end.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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

#905

On Mon, 20 May 2013 10:53:39 GMT, anton@mips.complang.tuwien.ac.at
(Anton Ertl) wrote:

[snip]

>That depends on the syntax of the language.  E.g., at one time
>Modula-2 was the language used in our introductory programming course
>25 years ago, our students used to write things like
>
>a<3 AND b<3

     I would do that.

>and the compiler reported a type error (a and b were of type INTEGER).
>But it really was a syntax error.  The students should have written
>
>(a<3) AND (b<3)

     Nasty.

>because the implicit binding was
>
>a<(3 AND b)<3
>
>and "3 AND b" was a type error.  This error message confused the
>students no end.

     Things like this are why I like details in the error messages
about what is being complained about, say:
     "3" is not of a valid type for the "and" operator.
     "b" is not of a valid type for the "and" operator.
That does not always help, but it usually does.

Sincerely,

Gene Wirchenko

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

#906 — precedence have both ways

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>a<3 AND b<3

This reminds me of a question.

One person designs a language 'C1' with precedence:

    [higher]
    ...
    |
    &
    <, <=, >, <=
    ==, !=
    ...
    [lower]

Some other person designs a language 'C2' with precedence:

    [higher]
    ...
    <, <=, >, <=
    ==, !=
    |
    &
    ...
    [lower]

They're the same besides that.

To compromise, they make a new language 'C3' such that a program is
valid C3 if it is valid C1 and valid C2 -and- both ways mean the same.

Is there some good way to do this -in the grammar-?

[I see gcc has warnings like this.]

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

#908 — Re: precedence have both ways

Joe keane <jgk@panix.com> wrote:

(snip)

> This reminds me of a question.

> One person designs a language 'C1' with precedence:
>
>    [higher]
>    ...
>    |
>    &
>    <, <=, >, <=
>    ==, !=
>    ...
>    [lower]

> Some other person designs a language 'C2' with precedence:

Looks not so far from B, see:

http://cm.bell-labs.com/cm/cs/who/dmr/bref.pdf

>    [higher]
>    ...
>    <, <=, >, <=
>    ==, !=
>    |
>    &
>    ...
>    [lower]

> They're the same besides that.

> To compromise, they make a new language 'C3' such that a program is
> valid C3 if it is valid C1 and valid C2 -and- both ways mean the same.

Seems easy if you disallow the use of the operators with changed
precedence without appropriate ()'s.

> Is there some good way to do this -in the grammar-?

As above, put the restriction in the grammar.

As I understand it, not having actually ever programmed in B,
(but found the reference manual) B only had the bitwise operators,
and shared them (used them also for) the logical operators.
The had (and have) the appropriate precedence.

When C inherited them from B, and then added the && and || operators,
the previous & and | operators kept their precedence. For actual use
as bitwise operators, such as masks, it would be more convenient if
they had higher precedence. As it is, they pretty much always are
parenthesized. (Easy to forget and generate wrong results.)

-- glen

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

#909 — Re: precedence have both ways

jgk@panix.com (Joe keane) writes:
>One person designs a language 'C1' with precedence:
>
>    [higher]
>    ...
>    |
>    &
>    <, <=, >, <=
>    ==, !=
>    ...
>    [lower]
>
>Some other person designs a language 'C2' with precedence:
>
>    [higher]
>    ...
>    <, <=, >, <=
>    ==, !=
>    |
>    &
>    ...
>    [lower]
>
>They're the same besides that.
>
>To compromise, they make a new language 'C3' such that a program is
>valid C3 if it is valid C1 and valid C2 -and- both ways mean the same.
>
>Is there some good way to do this -in the grammar-?

Sure, you don't want | & to asssociate with < <= > >= == != (I find
the remaining associations questionable, but let's stick with your
example).  So write the grammar in a way that makes the wanted
associations explicit and does not contain the unwanted associations:

boolexpr: orexpr
        | ineqexpr ;
orexpr: orexpr '|' andexpr
      | andexpr ;
andexpr: andexpr '&' lower
       | lower ;
ineqexpr: eqexpr ineqop eqexpr
        | eqexpr ;
eqexpr: lower eqop lower
      | lower ;
...
term: '(' highest ')'
    | ... ;

(This assumes that a<b<c and a==b==c is not wanted; also, resolving
conflicts is left as an exercise).

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web