Agreement in English grammar

In English, nouns, pronouns and verbs have attributes such as grammatical number, gender, and person, which must agree between subject, main verb, and pronouns referring to the subject:

• I wash myself.
• She washes herself.
• We wash ourselves.

are valid sentences; invalid are, for instance:

• *I washes ourselves.
• *She wash himself.
• *We wash herself.

Here, agreement serves to stress that both pronouns (e.g. I and myself) refer to the same person.

A context-free grammar to generate all such sentences:

<sentence> ::= <subject> <verb> <object>
<subject>  ::= I | You | He | She | We | They
<verb>     ::= wash | washes
<object>   ::= myself | yourself | himself | herself | ourselves | yourselves | themselves

From sentence, we can generate all combinations:

I wash myself
I wash yourself
I wash himself
[...]
They wash yourselves
They wash themselves

A W-grammar to generate only the valid sentences:

<sentence <NUMBER> <GENDER> <PERSON>>
  ::= <subject <NUMBER> <GENDER> <PERSON>>
      <verb <NUMBER> <PERSON>>
      <object <NUMBER> <GENDER> <PERSON>>

<subject singular <GENDER> 1st> ::= I
<subject <NUMBER> <GENDER> 2nd> ::= You
<subject singular male 3rd>     ::= He
<subject singular female 3rd>   ::= She
<subject plural <GENDER> 1st>   ::= We
<subject singular <GENDER> 3rd> ::= They

<verb singular 1st>    ::= wash
<verb singular 2nd>    ::= wash
<verb singular 3rd>    ::= washes
<verb plural <PERSON>> ::= wash

<object singular <GENDER> 1st> ::= myself
<object singular <GENDER> 2nd> ::= yourself
<object singular male 3rd>     ::= himself
<object singular female 3rd>   ::= herself
<object plural <GENDER> 1st>   ::= ourselves
<object plural <GENDER> 2nd>   ::= yourselves
<object plural <GENDER> 3rd>   ::= themselves

<NUMBER> ::== singular | plural
<GENDER> ::== male | female
<PERSON> ::== 1st | 2nd | 3rd

A standard non-context-free language

A well-known non-context-free language is

${\displaystyle \{a^{n}b^{n}a^{n}|n\geq 1\}.}$

A two-level grammar for this language is the metagrammar

N ::= 1 | N1

X ::= a | b

together with grammar schema

Start ::= ${\displaystyle \langle a^{N}\rangle \langle b^{N}\rangle \langle a^{N}\rangle }$

${\displaystyle \langle X^{N1}\rangle }$ ::= ${\displaystyle \langle X^{N}\rangle X}$

${\displaystyle \langle X^{1}\rangle }$ ::= X

Requiring valid use of variables in ALGOL

The Revised Report on the Algorithmic Language Algol 60^[10] defines a full context-free syntax for the language.

Assignments are defined as follows (section 4.2.1):

<left part>
  ::= <variable> :=
    | <procedure identifier> :=

<left part list>
  ::= <left part>
    | <left part list> <left part>

<assignment statement>
  ::= <left part list> <arithmetic expression>
    | <left part list> <Boolean expression>

A <variable> can be (amongst other things) an <identifier>, which in turn is defined as:

<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>

Examples (section 4.2.2):

s:=p[0]:=n:=n+1+s
n:=n+1
A:=B/C-v-q×S
S[v,k+2]:=3-arctan(sTIMESzeta)
V:=Q>Y^Z

Expressions and assignments must be type checked: for instance,

• in n:=n+1, n must be a number (integer or real);
• in A:=B/C-v-q×S, all variables must be numbers;
• in V:=Q>Y^Z, all variables must be of type Boolean.

The rules above distinguish between <arithmetic expression> and <Boolean expression>, but they cannot verify that the same variable always has the same type.

This (non-context-free) requirement can be expressed in a W-grammar by annotating the rules with attributes that record, for each variable used or assigned to, its name and type.

This record can then be carried along to all places in the grammar where types need to be matched, and implement type checking.

Similarly, it can be used to checking initialization of variables before use, etcetera.

One may wonder how to create and manipulate such a data structure without explicit support in the formalism for data structures and operations on them. It can be done by using the metagrammar to define a string representation for the data structure and using pattern matching to define operations:

<left part with <TYPED> <NAME>>
  ::= <variable with <TYPED> <NAME>> :=
    | <procedure identifier with <TYPED> <NAME>> :=

<left part list <TYPEMAP1>>
  ::= <left part with <TYPED> <NAME>>
      <where <TYPEMAP1> is <TYPED> <NAME> added to sorted <EMPTY>>
    | <left part list <TYPEMAP2>>
      <left part with <TYPED> <NAME>>
      <where <TYPEMAP1> is <TYPED> <NAME> added to sorted <TYPEMAP2>>

<assignment statement <ASSIGNED TO> <USED>>
  ::= <left part list <ASSIGNED TO>> <arithmetic expression <USED>>
    | <left part list <ASSIGNED TO>> <Boolean expression <USED>>

<where <TYPED> <NAME> is <TYPED> <NAME> added to sorted <EMPTY>>
  ::=

<where <TYPEMAP1> is <TYPED1> <NAME1> added to sorted <TYPEMAP2>>
  ::= <where <TYPEMAP2> is <TYPED2> <NAME2> added to sorted <TYPEMAP3>>
      <where <NAME1> is lexicographically before <NAME2>>

<where <TYPEMAP1> is <TYPED1> <NAME1> added to sorted <TYPEMAP2>>
  ::= <where <TYPEMAP2> is <TYPED2> <NAME2> added to sorted <TYPEMAP3>>
      <where <NAME2> is lexicographically before <NAME1>>
      <where <TYPEMAP3> is <TYPED1> <NAME1> added to sorted <TYPEMAP4>>

<where <EMPTY> is lexicographically before <NAME1>>
  ::= <where <NAME1> is <LETTER OR DIGIT> followed by <NAME2>>
 
<where <NAME1> is lexicographically before <NAME2>>
  ::= <where <NAME1> is <LETTER OR DIGIT> followed by <NAME3>>
      <where <NAME2> is <LETTER OR DIGIT> followed by <NAME4>>
      <where <NAME3> is lexicographically before <NAME4>>

<where <NAME1> is lexicographically before <NAME2>>
  ::= <where <NAME1> is <LETTER OR DIGIT 1> followed by <NAME3>>
      <where <NAME2> is <LETTER OR DIGIT 2> followed by <NAME4>>
      <where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 2>

<where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 2>
  ::= <where <LETTER OR DIGIT 1> precedes <LETTER OR DIGIT 2>

<where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 2>
  ::= <where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 3>
      <where <LETTER OR DIGIT 3> precedes+ <LETTER OR DIGIT 2>

<where a precedes b> :==
<where b precedes c> :==
[...]

<TYPED>       ::== real | integer | Boolean

<NAME>        ::== <LETTER> | <NAME> <LETTER> | <NAME> <DIGIT>
<LETTER OR DIGIT> ::== <LETTER> | <DIGIT>
<LETTER OR DIGIT 1> ::= <LETTER OR DIGIT>
<LETTER OR DIGIT 2> ::= <LETTER OR DIGIT>
<LETTER OR DIGIT 3> ::= <LETTER OR DIGIT>
<LETTER>      ::== a | b | c | [...]
<DIGIT>       ::== 0 | 1 | 2 | [...]

<NAMES1>      ::== <NAMES>
<NAMES2>      ::== <NAMES>
<ASSIGNED TO> ::== <NAMES>
<USED>        ::== <NAMES>
<NAMES>       ::== <NAME> | <NAME> <NAMES>

<EMPTY>       ::==
<TYPEMAP>     ::== (<TYPED> <NAME>) <TYPEMAP>
<TYPEMAP1>    ::== <TYPEMAP>
<TYPEMAP2>    ::== <TYPEMAP>
<TYPEMAP3>    ::== <TYPEMAP>

When compared to the original grammar, three new elements have been added:

• attributes to the nonterminals in what are now the hyperrules;
• metarules to specify the allowable values for the attributes;
• new hyperrules to specify operations on the attribute values.

The new hyperrules are ${\displaystyle \epsilon }$-rules: they only generate the empty string.

ALGOL 68 as in the 1968 Final Report §2.1

a) program : open symbol, standard prelude,
      library prelude option, particular program, exit,
      library postlude option, standard postlude, close symbol.
 b) standard prelude : declaration prelude sequence.
 c) library prelude : declaration prelude sequence.
 d) particular program :
      label sequence option, strong CLOSED void clause.
 e) exit : go on symbol, letter e letter x letter i letter t, label symbol.
 f) library postlude : statement interlude.
 g) standard postlude : strong void clause train

ALGOL 68 as in the 1973 Revised Report §2.2.1, §10.1.1

 program : strong void new closed clause

 A) EXTERNAL :: standard ; library ; system ; particular.
 B) STOP :: label letter s letter t letter o letter p.

 a) program text : STYLE begin token, new LAYER1 preludes, 
        parallel token, new LAYER1 tasks PACK, 
        STYLE end token.
 b) NEST1 preludes : NEST1 standard prelude with DECS1, 
        NEST1 library prelude with DECSETY2, 
        NEST1 system prelude with DECSETY3, where (NEST1) is
        (new EMPTY new DECS1 DECSETY2 DECSETY3).
 c) NEST1 EXTERNAL prelude with DECSETY1 : 
        strong void NEST1 series with DECSETY1, go on token ; 
        where (DECSETY1) is (EMPTY), EMPTY.
 d) NEST1 tasks : NEST1 system task list, and also token, 
        NEST1 user task PACK list.
 e) NEST1 system task : strong void NEST1 unit.
 f) NEST1 user task : NEST2 particular prelude with DECS, 
        NEST2 particular program PACK, go on token, 
        NEST2 particular postlude, 
        where (NEST2) is (NEST1 new DECS STOP).
 g) NEST2 particular program : 
        NEST2 new LABSETY3 joined label definition
        of LABSETY3, strong void NEST2 new LABSETY3
        ENCLOSED clause.
 h) NEST joined label definition of LABSETY : 
        where (LABSETY) is (EMPTY), EMPTY ; 
        where (LABSETY) is (LAB1 LABSETY1), 
           NEST label definition of LAB1, 
           NEST joined label definition of$ LABSETY1. 
 i) NEST2 particular postlude :
        strong void NEST2 series with STOP.

A simple example of the power of W-grammars is clause

a) program text : STYLE begin token, new LAYER1 preludes, 
       parallel token, new LAYER1 tasks PACK, 
       STYLE end token.

This allows BEGIN ... END and { } as block delimiters, while ruling out BEGIN ... } and { ... END.

One may wish to compare the grammar in the report with the Yacc parser for a subset of ALGOL 68 by Marc van Leeuwen.^[11]