Talk:Van Wijngaarden grammar

Although this formalism is historically associated with Algol 68, it is technically just a particular type of grammar formalism; the article should really devote itself to describing the formalism and giving examples, with the Algol 68 connection dangling somewhere at the bottom. Help is welcomed ... Rp (talk) 15:14, 9 July 2008 (UTC)

Broken link for A W-Grammar Description for ADA

In References section, the link for “A W-Grammar Description for ADA” is broken. I searched the web and could find nothing available on‑line. Should the link be removed a reference be given without a link? --Hibou57 (talk) 09:00, 24 February 2013 (UTC)

re: "reference without a link", yes that would be reasonable. I changed the link to http://www.ntis.gov/search/product.aspx?ABBR=ADA177802 NevilleDNZ (talk) 09:42, 24 February 2013 (UTC)

Merging “Two-level grammar” into this article

Two-level grammar has not develeloped as an independent standalone article. It looks as if it could be merged into this article (by someone who knows the topic) —Northernhenge (talk) 20:21, 4 January 2023 (UTC)

Good idea. I only know what we were taught by Kees Koster when I studied in Nijmegen in the 80s. Another candidate for merging is affix grammar. He distinguished between affix grammars and attribute grammars by saying in affix grammars you specify the construction of attribute values within the grammar rules, while in attribute grammars you don't. Van Wijngaarden grammars are a particular type of affix grammar and as far as I recall, Koster considered two-level grammars and Van Wijngaarden grammars to be synonyms, so I definitely think they ought to be merged. Rp (talk) 11:55, 5 January 2023 (UTC)

Shall I just go ahead and do it? A very brief literature search confirms my suspicions that

• although at least one variant exists, the term two-level grammar almost always refers to Van Wijngaarden grammars;
• they have seen very little use outside the description of Algol 68, although some authors advocate their use as a declarative programming and specification language (more concise, expressive and general than Prolog);
• nothing appears to have been published on them in the last 25 years or so.

The remaining question for me is whether to call the resulting article Two-level grammar or Van Wijngaarden grammar. (The other term will be a redirection.) Rp (talk) 18:18, 12 January 2023 (UTC)

I support the merger but I don’t know the subject well enough to attempt it. Please go ahead. The Van Wijngaarden grammar article is better-developed and its name is more specific to what is being discussed, so I suggest adding the relevant content from Two-level grammar into Van Wijngaarden grammar and replacing Two-level grammar with a redirect. It would be more work to do it the other way round. —Northernhenge (talk) 19:13, 12 January 2023 (UTC)

I went ahead and incorporated the two-level grammar stub, extending the article in the process. This took a full weekend (in which I had hoped to do other things). Please review! Rp (talk) 12:52, 20 February 2023 (UTC)

Wow – great job! It’s not a subject I’m currently very familiar with, though I did have some understanding of it a few decades ago. I’ve made some comments here. I hope they don’t read as negative.

The structure of the article is:

1. Motivation
2. Examples not from Algol68 (English; formal notation(?); Algol(60?)
3. Examples from Algol68
4. Implementations
5. Applications outside of ALGOL 68

Section 1 is quite technical. Maybe it should start by looking in plain english at what problems van Wijngaarden was trying to solve.

Section 2 reads more like a tutorial than an encyclopaedia article and could be considerably briefer. The formal notation section seems unnecessary, or maybe it needs to be there so needs more explanation.

Sections 3 and 5 both seem to cover similar ground to each other using different examples so could be combined.

As I say, this isn’t my field but I thought the two levels were the metaproduction rules and the production rules. The lede says the two levels are the hyper-rules and the meta-rules but McGettrick https://books.google.co.uk/books?id=Y2ieBQAAQBAJ&pg=PP6 says metaproduction and production (top of page 24)

I hope none of that sounds negative!!! -- Northernhenge (talk) 21:14, 14 March 2023 (UTC)

Not at all, good suggestions! I am also going by 35 year old memory and references found with Google, so any help is appreciated. I've been busy but I will attempt another rewrite when I find the time, if nobody beats me to it. Rp (talk) 08:06, 26 March 2023 (UTC)

I'm looking at the task now, and this is my proposal.

• The introduction will stay as it is. Is it clear enough? Does it need the detail it has right now? The detail is included because I feel the name two-level grammar needs to be explained.
• Next, there will be just the examples, without the motivation. I admit these read like a tutorial, but without the examples, the whole article (e.g. the motivation) will only make sense to readers with sufficient prior training in formal language theory. Articles should be aimed at a general audience.
• Next, the Motivation section. I don't think I can make the untrained reader understand the motivation (which is that standard context-free grammar isn't expressive enough and that attributes solve this) without the examples. This section:
  • should probably start by explaining the problem of parsing and interpreting languages and the idea of generating parsers based on explicit grammars; this is prerequisite knowledge covered in separate articles such as Compiler compiler, so it should be brief;
  • should then explain how attributes provide expressive power that standard context-free grammars lack, using the examples given earlier to illustrate this. This should explain how standard CFGs can't express agreement and how you need complex attribute values if you want to express constraints related to variables in a programming language.
• At this point, there should probably be a separate section to compare 2VWGs with other approaches:
  • 2VWGs add the attributes to the language and requires consistent substitution of attribute values within rules, and ta-da, by apparent magic, you can now suddenly express arbitrary constraints and complex operations on attribute values. This is weird, so it's worth demonstrating, which is why one of my examples does this. At this point there should be a discussion how this is related to constraint satisfaction and logic programming (Prolog).
  • Other types of attribute grammars, e.g. Knuth's, add attributes, but leave their manipulation to code written in a programming language.
  • The traditional approach, still used in popular parser generators, implicitly adds and manipulates attributes in practice (in code), but without making them part of the grammar at all.
• Next, a section Reception which should mention how ALGOL 68 was specified in full with 2VWGs, but little else, and that overall, 2VWGs were rejected by practitioners as too baroque, too impractical, and too powerful. It would be nice to have a discussion of how 2VWGs or aspects of them live on today, or have been reinvented, but I'm not aware of any examples. Rp (talk) 20:19, 6 May 2023 (UTC)

Sounds like a good plan, and quite ambitious! Unfortunately all I know about these comes from looking at definite clause grammars in a logic programming context, although I do have a copy of A grammatical view on logic programming, which considers VWGs as a Turing complete programming language. Felix QW (talk) 19:55, 14 June 2023 (UTC)