On Saturday, November 23, 2019 at 10:36:28 PM UTC-6, Edward K. Ream wrote:
> > It's just a bit tricky to look ahead in a generator.
> Correction, it's amazingly tricky...For now, I'll just use helper lists:
Shortly after writing this the last piece of this particular puzzle
appeared. There is no need for either generators nor helper lists.
Doh! The so-called generators are nothing but indices into the token list.
There is no need for helper lists! peek and advance need only maintain an
integer index into the token list. This index monotonically advances,
guaranteeing O(N) performance, as explained in more detail in the Post
Script.
The code is still tricky. The following completely debugged *functions* are
defined *within *the do_If method.
def is_if(token):
return token.kind == 'name' and token.value in ('if', 'elif', 'else')
def find_next_if_token(i):
# Careful. there may be no 'if', 'elif' or 'else' tokens in the token
list.
while i < len(self.tokens):
if is_if(self.tokens[i]):
break
i += 1
return i
_index = find_next_if_token(0)
def advance():
nonlocal _index
_index = find_next_if_token(_index+1)
def peek():
nonlocal _index
# The possibility of an IndexError is a sanity check.
return self.tokens[_index]
Similar functions appear in the all-important tog.sync method.
*Timing*
The project is very fast. Indeed, TestRunner.run_tests reports the
following stats for some of Leo's source files:
description: file: core..leoFind.py
setup time: 0.17 sec.
link time: 0.09 sec.
description: file: core..leoGlobals.py
setup time: 0.58 sec.
link time: 0.41 sec.
description: file: core..runLeo.py
setup time: 0.00 sec.
link time: 0.00 sec.
The *setup time* is the time to tokenize the file with Python's tokenize
module, plus the time to parse the file with Python's ast module.
The *link time* is the time to traverse the entire tree. This is a figure
of merit for the entire project. As you can see, it is extremely fast.
*Summary*
Neither generators nor helper lists are required. It suffices to define
local helper *functions*, defined *within* visitor methods.
These helper functions are non-trivial, but all will be variants on the
debugged functions defined within do_If.
The entire traversal runs in time linear in the number of tokens and parse
tree nodes.
Edward
P.S. The code demonstrates that the running time of the helper functions is
O(N), where N is the number of tokens. Indeed, do_If will call peek and
advance a *bounded* number of times for each ast.If node in the tree. In
fact, the upper bound is 2 calls to peek and 2 calls to advance.
Finally, the _index pointer monotonically increases, so the bounded for the
*total
*number of iterations in find_next_token is N.
EKR
--
You received this message because you are subscribed to the Google Groups
"leo-editor" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/leo-editor/e09474a2-c171-4ebc-8eeb-dd9ec5ff1c1e%40googlegroups.com.
