3
\$\begingroup\$

I found lexy, a C++ template-based parser combinator, that helps a lot to build a language parser.

The problem is that lexy can only deal with context free grammar, and python indentation is not context free.

I wrote this small piece of code to generate indent/dedent tokens, represented by either { or }, so I can feed its output to lexy. As you can see, I had to add a trailing line return at the end of the input.

input_test1 = '''a
    b
    c
        d
        e
    f
        h
        g
            i
            j
    k
l
    m
        n
            o
            p
            q
r
    s
t'''

input_test2 = '''a
    b
    c
        d
        e
    f
        h
        g
            i
            j
    k
l
    m
        n
            o
            p
            q
r
    s
t
'''

input_test3 = '''a
    b
    c
        d
        e
    f
        h
        g
            i
            j
    k
l
    m
        n
            o
            p
            q
r
    s'''
input_test4 = '''a
    b
    c
        d
        e
    f
        h
        g
            i
            j
    k
l
    m
        n
            o
            p
            q
r
    s
'''


def token_indenter(source):
    if source[-1] != '\n':
        print('added\\n')
        source += '\n'
    lines = source.split('\n')
    lines = [line for line in lines]

    def leading_spaces(s):
        spaces = 0
        for c in s:
            if c == ' ':
                spaces += 1
            else:
                break
        return spaces//4
    lines = [(line, leading_spaces(line))
        for line in lines]
    # prev None . . . .
    # next  . . . . None

    lines = [
        (
            lines[i-1][1] if 1<=i<len(lines) else None, # prev: 1 to len-1
            lines[i+1][1] if 0<=i<len(lines)-1 else None, # next: 0 to len-2
            line, spaces
         )
        for (i, (line, spaces)) in enumerate(lines)]

    lines = [
        (spaces - prev if prev!=None else None,
        spaces - nextt if nextt!=None else None,
        line, spaces)
        for (prev, nextt, line, spaces) in lines]


    '''
        diffprev is about indent only
        diffprev(a):

        case 1: we care
            a
                b
            > 1

        case 2:
                a
            b
            > -1

        case 3:
                    a
            b
            > -2

        diffnext is about dedent only
        diffnext(a):

        case 1:
            a
                b
            > 1

        case 2: we care
                a
            b
            > -1

        case 3: we care
                    a
            b
            > -2


    '''

    lines_tokens = []
    # we only insert tokens on the same line to keep the context, hence redundancy
    for (diffprev, diffnext, line, spaces) in lines:
        dedent = 0
        indent = 0

        if diffprev == 1:
            indent = 1
        if diffnext:
            dedent = diffnext


        lines_tokens.append((line, diffprev, diffnext, indent, dedent, spaces))

    laidout = ''
    laidout_better = ''
    for (line, diffprev, diffnext, indent, dedent, spaces) in lines_tokens:

        indent_tok = '{' if indent else ''
        dedent_tok = '}'*dedent if dedent else ''
        symbol = line.replace(' ','')
        spaces_brace = spaces -1
        spaces*=4
        spaces_brace*=4
        cool_line = (
            (((' '*spaces_brace) + indent_tok + '\n') if indent_tok else '')
            +f'{line:<30} | spaces: {spaces}\n'
            +(((' '*spaces_brace) + dedent_tok + '\n') if dedent_tok else '')
            )
        laidout_better+=cool_line

        laidout += f'{indent_tok} {symbol} {dedent_tok}'

        diagnose = (f'{repr(line):<20} |  {indent_tok:4} {symbol:<4} {dedent_tok:4} diffprev {str(diffprev):>5} diffnext {str(diffnext):>5}')

        print(diagnose)

    print('----')
    # print(laidout)
    print('----')
    print(laidout_better)
    print('----')
    return laidout

result1 = token_indenter(input_test1)
result2 = token_indenter(input_test2)
result3 = token_indenter(input_test3)
result4 = token_indenter(input_test4)

print(result1 == result2)
print(result3 == result4)

'''
indent can be inserted
    only once per line
    at the beginning of the line
dedent can be inserted
    multiple times per line
    at the end of the line

'''

I'm looking for suggestions for improvements.

As you can see with this output:

{
    m                          | spaces: 4
    {
        n                      | spaces: 8
        {
            o                  | spaces: 12
            p                  | spaces: 12
            q                  | spaces: 12
        }}}
r                              | spaces: 0

Dedent tokens are grouped. It's not a problem because my parser will not care, but I'm not 100% sure, and it might be better for readability to ungroup them.

I'm still a bit in doubt about parsing multi line square-bracketed lists like:

[1, 3, 5
    4, 5, 6
    12, 34]
\$\endgroup\$
3
  • 1
    \$\begingroup\$ If your intent is to mimic Python's behaviour, then you would turn off INDENT/DEDENT production inside parenthesized expressions, for all three parenthetic constructs ((), [], {}). \$\endgroup\$
    – rici
    Dec 14, 2022 at 17:55
  • \$\begingroup\$ By turn off you mean just delete them in the output? \$\endgroup\$
    – jokoon
    Dec 15, 2022 at 9:56
  • \$\begingroup\$ Take a look at the function _tokenize() in tokenize.py from the standard library. The basic idea is to keep a stack of current indent levels. If the number of spaces at the beginning of a line is greater than the one on the top of the stack, emit an INDENT token and push the current indent on the stack. If less than the top of the stack, emit a DEDENT token and pop the stack until the indent matches the top of the stack. Depending on your end goal, maybe just use the tokenize module. \$\endgroup\$
    – RootTwo
    Dec 16, 2022 at 22:52

1 Answer 1

2
\$\begingroup\$

This code is really hard to read:

def token_indenter(source):
    if source[-1] != '\n':
        print('added\\n')
        source += '\n'
    lines = source.split('\n')
    lines = [line for line in lines]

    def leading_spaces(s):
        spaces = 0
        for c in s:
            if c == ' ':
                spaces += 1
            else:
                break
        return spaces//4
    lines = [(line, leading_spaces(line))
        for line in lines]
    # prev None . . . .
    # next  . . . . None

    ...

You have a function, which starts off with several lines of code, then after a blank line, an embedded function which is immediately followed by more code lines of the original function without any separation. Whitespace is your friend; use it. Also, don't split up code with other function definitions; move the embedded function declaration to the very start of the outer function ... or even move it out of the function entirely, since it can stand on its own as a useful function.


On the subject of whitespace, follow the PEP-8 guidelines of surrounding operators with a space. 0<=i<len(lines)-1 is a little too dense. 0 <= i < len(lines) - 1 is easier to read. Similarly, nextt!=None should be nextt != None, etc.


Blanks lines in input are not handled.

input_test1 = '''a
    b

    c
        d
        e

    f
        h
        g
            i
            j

    k

l
    m
        n
            o
            p
            q
r
    s
t'''

Can generate:

a                              | spaces: 0
{
    b                          | spaces: 4
}
                               | spaces: 0
{
    c                          | spaces: 4
    {
        d                      | spaces: 8
        e                      | spaces: 8
    }}
                               | spaces: 0
{
    f                          | spaces: 4
    {
        h                      | spaces: 8
        g                      | spaces: 8
        {
            i                  | spaces: 12
            j                  | spaces: 12
        }}}
                               | spaces: 0
{
    k                          | spaces: 4
}
                               | spaces: 0
...

which is very different from Python parsing behaviour.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.