Geek asks and answers

Can BNF handle direct consumption?

I recently discovered a python module pyparsing, a great tool for analyzing data by writing a grammar, not a parser. I am new to the concept of context-free grammars, so please correct any false assumptions in this matter.

Pyparsing can implement BNF ( Backsu-Naur Form ) contextual grammar. This grammar can be recursive, but can it have a forward-looking forecast? I was interested to know about this since I came across this question . Let me give you a concrete example. Consider the line:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Let the grammar look something like this:

<number> :: __<digit>__
<block>  :: <number>(x) (<number> <number> <number> .... x times)

i.e. read the first token of a number, save it as x, and then use the following numbers xand group them together. The designed line should look like this:

 [[1, 2], [3, 4, 5, 6], [7, 8, 9, 10, 11, 12, 13, 14], [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]

I wrote a simple Python MWE that does not use pyparsing, so what is clear what I'm trying to do:

A = range(1,31)

B, sub_b = [], []
consume  = 0

for a in A:
    if consume: 
        sub_b.append(a)
        consume -= 1
    else:
        if sub_b: B.append(sub_b)
        sub_b = [a,]
        consume = a
B.append(sub_b)
print B

Two (related) questions: Can this be done using a context-free BNF grammar? If yes / no, how can I do this with pyparsing?

+4
source share
3 answers

, - , , . , consume, CFG, , - . , , 1, 2, 3 ..:

<block3> :: <number> <number> <number>

, , -:

<block3a> :: 3 <number> <number> <number>
<block3b> :: <number> <number> <number> 3

... , , , , N, .

CFG . CFG ( BNF ), , . , , CFG " " . , N blockN , . CFG, .

,, - : . , . (), , ( , ).

(* * * 4 7 10), CFG :

<group> :: * <group> <number>
<group> :: * <number>

a^n b^n. , "" .. ( , ) , . , "21" . , CFG ( , ..), . , . , , .

+3

Pyparsing countedArray, , . expr , "n" expr. :

from pyparsing import *
from pprint import pprint

# make a long string of integers, starting at 0
source = ' '.join(map(str, range(50)))

# define an integer as a 'word' of numeric digits
integer = Word(nums)

# add a parse action to convert the parsed strings to integers, at parse time
integer.setParseAction(lambda t:int(t[0]))

# parse the source string into counted strings of integers, and print out
# with pprint
lists = OneOrMore(countedArray(integer)).parseString(source)
pprint(lists.asList())

:

[[],
 [2],
 [4, 5, 6],
 [8, 9, 10, 11, 12, 13, 14],
 [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]

  • , integer, ( ).

  • , "0" .

  • 30, .

countedArray , , , undefined Forward. , , expr*n Forward, "n". countedArray(Word(alphas)) parse "4 the quick brown fox", ['the', 'quick', 'brown', 'fox']. @Aaron , , , len .

pyparsing FollowedBy NotAny (NotAny "~" ). " ..." , , Word(alphas) + FollowedBy(Word('aeiou',alphas)), "score" "years"; , , Word(alphas) + ~Literal('.'), , "". , , searchString scanString parseString.

+3

.

, . , 1 - , 3?

:

[[2], [4, 5, 6], [8, 9, 10, 11, 12, 13, 14], [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]

and the grammar will look like this:

<model> :: <term>
<list>  :: <term> | <term> <opt-whitespace> <list>
<term>  :: '[' <list> ']'

You can then restore the missing count element by looking at the length of the list.

+1
source

More articles:


All Articles