Search code examples
bnf

BNF accepting a list( infinite amount of vars) and append(infinite amount of lists) but not append(symbol)?


I am trying to write a BNF that contains a List and append func':

The list is supposed to get as many symbols, lists or numbers as wanted: Therefore I wrote something like this:

<LIST> ::= <SNS>
         | <APPEND>
         | (list <SNS>)
         | (list <LIST>)
         | (list <SNS> <LIST>)

The append is supposed to get as many lists as possible therefore I wrote something like:

<APPEND>::= 
            <LIST>
          | (append <LIST>)
          | (append <LIST> <APPEND>)

The language accepts also symbols numbers or null therefore I wrote:

<SNS> ::= <null>
        | <num>
        | '<sym>

My problem is that part of the requests on this BNF is that it should not accept (append <num>).


The way I fixed this is to do:

<LIST> ::= <null>                  //this is a list therefore (append null) is good
         | <APPEND>                // also is a list
         | <LIST>
         | (list <SNS>)
         | (list <LIST>)
         | (list <SNS> <LIST>)

<APPEND>::= (append <LIST>)
          | <LIST>
          | (append <LIST> <APPEND>)

The problem is that the BNF also tells me that I need to take in for an example: (list 1 33 `g).


How can I create a BNF that takes in both restrictions? What is the idea behind the fix?


Solution

  • Well I added a helper expression that basically is a flow of (symbols numbers or null).

    Instead of making the base of expression as I made that the func` list gets as input this flow of input.

    Old expression:

    <LIST> ::= <null>                  //this is a list therefore (append null) is good
             | <APPEND>                // also is a list
             | <LIST>
             | (list <SNS>)
             | (list <LIST>)
             | (list <SNS> <LIST>)
    
    <APPEND>::= (append <LIST>)
              | <LIST>
              | (append <LIST> <APPEND>)
    

    BNF - with new expression

    <LIST> ::= <null>
             | <CONS>
             | <APPEND>
             | (list <SNS_FLOW>)            ; this is what will get (list 1 2 ...)
             | (list <LIST>)                
             | (list <SNS_FLOW> <LIST>)     ; so I can accept: (list 'a (list ...))
             | (list <LIST> <SNS_FLOW>)     ; so I can accept: (list (list ...) 'a)
    
    <APPEND>::= (append <LIST>)
              | <LIST>
              | (append <LIST> <APPEND>)
    
    <SNS_FLOW>::= <SNS>                     ; this is the new expression
                | <SNS><SNS_FLOW>