# Controlling Recursion With Grammars for Data Generation

Note: Ignore the 200+ minute estimated read time :^), a few code samples bump it from 7 minutes to 200+.

I had been wanting for years to blog about my solution to a problem that I encountered in developing and using gramfuzz, where the maximum recursion depth of a grammar needed to be controlled.

Recently I was reading about Brandon Falk’s fzero fuzzer where he mentions that the F1 Fuzzer paper, “Building Fast Fuzzers”, by Rahul Gopinath and Andreas Zeller describes:

a technique that will resolve to the nearest terminal tokens when stack depth is exceeded

A quote from the paper:

Unfortunately, this simple approach has a problem when dealing with highly recursive grammars. As the fuzzer uses the recursion as a method to explore nested structures, it can deplete the stack quite fast. This can be fixed by limiting the alternatives explored to the lowest cost alternatives

The paper’s approach seems identical to what I had implemented in gramfuzz.

In this post I walk through gramfuzz’s implementation and provide concrete examples of its impact on controlling recursive limits during data generation when using grammars.

## Scenario

Grammars are recursive. Consider the BNF grammar (with a similar grammar in the gramfuzz examples) below that defines U.S. postal addresses:

 <postal-address> ::= <name-part> <street-address> <zip-part>
<name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> | <personal-part> <name-part>
<personal-part> ::= <initial> "." | <first-name>
<street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL>
<zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL>
<opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | ""
<opt-apt-num> ::= <apt-num> | ""


Notice how the name-part rule is recursive:

<name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> | <personal-part> <name-part>


If you were to write a tool to randomly generate data using this grammar, how might you limit the number of name-parts that are allowed?

Recursion within grammars isn’t limited to a single rule. Deep chains of referenced rules are also inevitable when randomly generating data from grammars.

## Data Generation With Grammars

The very basic grammar below defines strings similar to baa* blacksheep:

<baa_baa_blacksheep> ::= <baa_baa_list> "blacksheep"
<baa_baa_list> ::= <baa_baa_list> "baa" | "baa"


Suppose the rule <baa_baa_blacksheep> was identified as the rule to start generation from. Our code might look something like this:

def generate_rule(expr):
# all rules/expressions are ANDs by default, joined by spaces
if isinstance(expr, (OR, AND)):
return " ".join(generate_rule(sub_expr) for sub_expr in choose_exprs(expr))
else:
return rule.value

def choose_exprs(expr):
if isinstance(expr, OR):
return random_choose_one(expr.sub_exprs)
return rule.sub_exprs

rule = lookup_rule("<baa_baa_blacksheep>")
generate_rule(rule)


A stack trace of generating the last baa in the string baa baa baa baa blacksheep would look something like this:

4. generate_rule(<Expr OR baa_baa_list>)        baa baa baa baa blacksheep
chose 2nd OR'd expr, "baa"
3. generate_rule(<Expr OR baa_baa_list>)        ... baa baa baa blacksheep
chose 1st OR'd expr, <baa_baa_list> "baa"
2. generate_rule(<Expr OR baa_baa_list>)        ... baa baa blacksheep
chose 1st OR'd expr, <baa_baa_list> "baa"
1. generate_rule(<Expr OR baa_baa_list>)        ... baa blacksheep
chose 1st OR'd expr, <baa_baa_list> "baa"
0. generate_rule(<Expr AND baa_baa_blacksheep>) ... blacksheep


Since we are randomly choosing which OR'd expression of the <baa_baa_list> rule to generate, there’s a small chance that we could exceed the stack limit of our program by generating too many baas!

We could try a simple modification:

def choose_exprs(expr):
try:
if isinstance(expr, OR):
return random_choose_one(expr.sub_exprs)
return rule.sub_exprs
except RecursionError:
return []


This may work, but is heavy handed and would not let us gracefully choose the direct, or shortest, path out of the current rule being generated.

Ideally, we could have something similar to:

def choose_exprs(expr):
if isinstance(expr, OR):
if CURRENT_DEPTH > MAX_DEPTH:
return choose_shortest_path(expr)
return random_choose_one(expr.sub_exprs)
return rule.sub_exprs


## Shortest Path

In order to have something similar to the code above ^, the rules in the grammar must be preprocessed to calculate the shortest reference path of each rule.

### Preprocessing Reference Depths

Consider the rules below:

<window_document> ::= "window.document"
<this_document> ::= "this.document"
<new_document> ::= "new Document()"
<document_body_parentNode> ::= <document> ".body.parentNode"
<document> ::= <window_document> | <this_document> | <new_document> | <document_body_parentNode>

<document_createElement> ::= <document> ".createElement(\"" <tag-name> "\")"
<document_getElementById> ::= <document> ".getElementById(" <tag-id> ")"
<new_image> ::= "new Image()"
<element> ::= <new_image> | <document_createElement> | <document_getElementById> | <random_element>
<element_appendChild> ::= <element> ".appendChild(" <element> ")"

<random_element> :: = "rand([...document.getElementsByTagName('*')])"
<tag_name> ::= "[... new Set([...document.getElementsByTagName('*')].map(x => x.tagName))]"
| "h1" | "h2" | "img" | "div" | "br" | "span" | "canvas" | "form"
<tag_id> ::= "[...document.getElementsByTagName('*')].map(x => x.id)"


To calculate the shortest reference paths for all rules in the grammar, all leaf nodes within the defined rules must be identified. Leaf rules are rules that do not contain references to other rules. In the example above, the following are leaf nodes/rules:

• window_document
• this_document
• new_document
• new_image
• tag_name
• tag_id
• random_element

This is clearly demonstrated in the relationship graph below:

Each leaf rule has a “reference depth” of 0.

Next, all references within the remaining non-leaf rules are processed to determine their “reference depth”. If a rule contains multiple expressions joined by OR operators, each OR'd expression is processed separately, with the expressions having the lowest “reference depth” being used for the rule itself:

Rule Shortest Expression(s) Ref Depth
<window_document> "window.document" 0
<this_document> "this.document" 0
<new_document> "new Document()" 0
<new_image> "new Image()" 0
<document> <window_document> , <this_document> , <new_document> 1
<element> <new_image> 1
<document_body_parentNode> <document> ".body.parentNode" 2
<document_createElement> <document> ".createElement(\"" <tag-name> "\")" 2
<document_getElementById> <document> ".getElementById(" <tag-id> ")" 2
<element_appendChild> <element> ".appendChild(" <element> ")" 2

The reference depths shown for the rules above can be used to exit a rule’s generation in the most direct way possible.

### Exiting Directly

With reference depths calculated for each rule, cleanly exiting rule generation once a depth limit has been reached is nearly as straightforward as the sample generation example from earlier.

In gramfuzz, the Ref class tracks tracks the current reference depth, and sets the shortest flag to utils.val to True if the current reference level is greater than the maximum allowed:

REF_LEVEL = 1
class Ref(Field):
# ...
def build(self, pre=None, shortest=False):
"""Build the Ref instance by fetching the rule from
the GramFuzzer instance and building it
:param list pre: The prerequisites list
:param bool shortest: Whether or not the shortest reference-chain (most minimal) version of the field should be generated.
"""
global REF_LEVEL
REF_LEVEL += 1

try:
# ...
definition = self.fuzzer.get_ref(self.cat, self.refname)
res = utils.val(
definition,
pre,
shortest=(shortest or REF_LEVEL >= self.max_recursion)
)
return res

# this needs to happen no matter what
finally:
REF_LEVEL -= 1


The shortest=True value is passed into every field’s build() function. Each field class (And, Or, Join) propagates the shortest value to all build calls that field class makes.

The Or class is the only field that makes use of the shortest value in its build() function:

class Or(Field):
"""A Field subclass that chooses one of the provided values
at random as the result of a call to the build() method.
"""
# ...
def build(self, pre=None, shortest=False):
"""Build the Or instance
:param list pre: The prerequisites list
:param bool shortest: Whether or not the shortest reference-chain (most minimal) version of the field should be generated.
"""
if pre is None:
pre = []

# self.shortest_vals will be set by the GramFuzzer and will
# contain a list of value options that have a minimal reference
# chain
if shortest and self.shortest_vals is not None:
return utils.val(rand.choice(self.shortest_vals), pre, shortest=shortest)
else:
return utils.val(rand.choice(self.values), pre, shortest=shortest)


Gramfuzz includes a few examples in its source tree:

examples/
├── example.py
└── grams
├── bizbs.py
├── names.py
├── postal.py
├── python_2.7.13_grammar.txt
├── python27.py
└── roman_numeral.py


This section shows a few samples of the grammars generated with different maximum recursion values.

### BizBS - Business BS Grammar

Reference depths for the bizbs example grammar:

rule ref depth
verb 0
noun 0
sub_conjunction 0
present_participle 0
bizbs_part 0
bizbs_part_pres_participle 0
bizbs_phrase 1

> python examples/example.py -g bizbs -n 10 -s 1337 --max-recursion 2 scale leadership scale channels while unleashing users extend leadership skills though pursuing technology supply technology utilize alignments before recaptiualizing growth strategies target architectures since facilitating data engineer ROI since initiating "outside the box" thinking initiate channels parallel task synergy maintain systems until branding ROI  #### BizBS Reference Depth: 10 > python examples/example.py -g bizbs -n 10 -s 1337 --max-recursion 10
harness users nor compellingly matrixing users

impact virtual functionalities but assertively enhancing paradigms

pursue growth strategies once uniquely architecting synergistic schemas

distinctively coordinate best practices as long as cloudifying mission-critical fungibility

authoritatively provide access to impactful niches as credibly whiteboarding cloudified web services

uniquely dinintermediate disseminate functionalities unless transforming innovation

holisticly embrace total linkage even if e-enabling testing procedures

interactively architect corporate collaboration and idea-sharing till customizing solutions

incentivize real-time clouds


### Python 2.7

Reference depths for the python 2.7 example grammar:

rule ref depth
atom 0
augassign 0
break_stmt 0
comp_op 0
continue_stmt 0
dotted_name 0
except_clause 0
flow_stmt 0
fpdef 0
global_stmt 0
import_as_name 0
import_from 0
name 0
number 0
parameters 0
pass_stmt 0
raise_stmt 0
return_stmt 0
sliceop 0
small_stmt 0
string 0
subscript 0
trailer 0
varargslist 0
yield_expr 0
decorator 1
dotted_as_name 1
fplist 1
import_as_names 1
import_stmt 1
power 1
simple_stmt 1
subscriptlist 1
yield_stmt 1
decorators 2
dotted_as_names 2
factor 2
stmt 2
suite 2
classdef 3
file_input 3
funcdef 3
import_name 3
term 3
try_stmt 3
arith_expr 4
compound_stmt 4
decorated 4
shift_expr 5
and_expr 6
xor_expr 7
expr 8
comparison 9
exec_stmt 9
exprlist 9
del_stmt 10
not_test 10
and_test 11
or_test 12
comp_for 13
old_test 13
test 13
arglist 14
argument 14
assert_stmt 14
comp_if 14
comp_iter 14
dictorsetmaker 14
if_stmt 14
lambdef 14
list_if 14
listmaker 14
old_lambdef 14
print_stmt 14
testlist1 14
testlist 14
testlist_comp 14
testlist_safe 14
while_stmt 14
with_item 14
expr_stmt 15
for_stmt 15
list_for 15
list_iter 15
with_stmt 15

$> python examples/example.py -g python27 -n 1 -s 1337 --max-recursion 2 pass pass pass pass pass pass  #### Python27 Reference Depth: 10 $> python examples/example.py -g python27 -n 1 -s 1337 --max-recursion 10
class OzeGSQwzz((  )  and not 45  and BsV  and not 82  and CLyOy  and (  )  and not "jDfP"  and {  }  and [  ]   if not (  )  else (  )  or [  ]   or (  )  or {  }  or [  ]   or [  ]   or 3  and {  }  and 254  and [  ]   or 29  and "N"  and (  )  and -55  and (  )  and "tKkEItzI"  and {  } , not -88  and not "ojUk"  and not {  }  and "YdOLNuFWerJ"  and HvOELAoi  and [  ]   and not (  )  and not {  }  and not (  )  and uYsZ , -78  or not (  )  and (  )  and "ovTMWbEioW"  and not [  ]   and not (  )  and mQcS  and not zeZxGaB  and [  ]   or 92  and "BXeGWpnPJrlzrn"  and not -256  and not 256  and UnWXtat  and {  }  and not "nbRCs"  and not {  }  or oTecYE  and (  )  and not [  ]   and not 92  or [  ]   or not "kKyc"  and "a"  and {  }  and 85  or "IGcIjZRpW"  if -256  and not {  }  or (  )  or "fePyImQiYwJRIe"  else -39  and [  ]   and 77  and (  )  or {  }  or [  ]   and "dWKhziQXPn"  and uMkW  or 38  or (  )  and [  ]   and "xAK"  or [  ]  , lambda (bLzNefTGp), (cBNW), (eit)=lambda : -71 , mEPlBZbkM="D"  if (  )  else (  ) , (CbiJxjSqX)=(  ) , inUus, tcEsHBOZ, (bJzKWBPlc)=lambda : [  ]  , : 3  if [  ]   or "eaxTeseRQoufrCe"  or {  }  or qpQVoDBrQ  or {  }  or "RDtAapvLGb"  or {  }  or 98  or -83  else [  ]  , lambda (SssZdrKp)="twSFEltPl"  if "lmpGi"  else 9 , nibK=lambda : "Wn" , HzSTywD, (JbjxsXXd)=(  ) , PhGTa=lambda : (  ) , BBXyznOc=(  )  if {  }  else -78 , (RdRJg), (IvC), *KAC: "D"  or (  ) ):
global aTv;
with {  } , (  )  as [  ]  :
pass
pass
pass
pass
pass
pass
pass
pass
pass

assert {  } , -31 ;
@xsN
@QfhH
@rvllBq
@mKbxZN
@lHgkRWkz
@bTow
@VESaO
@aoFwrdOp
@zyvriRGbE
def QpPOvpjk():pass
from . import  * ;
if "oqZKPwZi" :pass

del (  ) , {  }  & 256  & 20  & LtECMp  & kBTFuaNbX  | "dDTCiMikktH"  & MPooKWlT  & (  )  & 26  & {  }  & -39  ^ [  ]   ^ wwXqDqkD  | 128  ^ ccQ  ^ (  )  | {  }  & -255  & [  ]   & (  )  & {  }  & [  ]   & -21  & (  )  & -1  | (  )  ^ {  }  & [  ]   & (  )  & TCJsgyid  ^ CmF  & "GQQNYSkaM"  & XUhVwN  & [  ]   ^ "lifHtzsUv"  | {  }  ^ RAEVkPfhA  ^ "y"  & [  ]   & gCnQVf  & -68  & (  )  & (  )  & 126  & "NooxSLUbAAAvcsRrO"  ^ 127  & 76  & 30  & (  )  ^ -257  ^ -52  | (  )  ^ cKkVm  ^ -4  & weirCNbD  & tQVz  & "tFJErmCfCu"  & (  )  & {  }  ^ VpOpSivq  & "HIKe"  & {  }  & aNp  & [  ]   & "BvcGIeZkUnw"  & "fnMFQYQFNj"  ^ "jhYXvaogkBppf"  & -3  & FOFmxb  & lsXm  & {  }  & [  ]  , ""  & {  }  & [  ]   & (  )  ^ {  }  & -130  & (  )  & -60  & (  )  & [  ]   & QNgeMuiI  & "YOeic"  & (  )  & 59  ^ (  )  & "pWkw"  & (  )  & [  ]   & {  }  ^ "FFbMqYH"  & wQApauZSs  & bBfzMU  & (  )  & pqZp  ^ [  ]   & {  }  & (  )  & {  }  & GZqzYOfS  ^ 0  & [  ]   & -77  & [  ]   & mJUFCKJ  & "kzkZeqT"  & Msc  & -98  & "TU"  & [  ]   & 256  | MKSrh  | ""  & -2  ^ {  }  & -66  & {  }  & ""  & [  ]   & (  )  & (  )  & (  )  & {  }  & [  ]   & [  ]   ^ {  }  ^ AfLRDZB  & {  }  & (  )  & 87  & -77  & (  )  & -45  & [  ]   ^ -99  ^ 81  & {  }  & "KsAXcERljXqL"  & [  ]   & {  }  & oVnmoMeA  & "gSHIuzZbaEqujwHBTl"  & vNVZUQ  ^ {  }  ^ "SuZPqVjQWUgbwHe"  & (  )  & QLD  & [  ]   & (  )  & (  )  & (  )  & [  ]   ^ (  )  ^ {  } , mrH  & [  ]   & "RINklKO"  & 254  | (  )  & (  )  & [  ]   & (  )  & "gYOeeuKbxUrMkUqYc"  & (  )  & -34  & (  )  ^ 64  & 27  & EOoVojZEW  & "AbPSyLg"  & -53  & {  }  & {  }  & -30  & {  }  & (  )  & mPVb  ^ {  }  & uxKBfUW  & 257  & "UNiLmbDzjBDnZGPnmqDaSQXtNvwReNHUavmAUACIhfxYAgLxvFxRmzEhaQzYLKnIIytaEBSDTxm"  & [  ]   & -127  & SSHRcEHn  & "RqLGuFObWsjRkHDfKF"  & xTvRPJTAv  & {  }  & [  ]   ^ [  ]   & 42  & [  ]   & Vueojow  & (  )  & [  ]   & (  )  ^ "a"  & {  }  & 72  & {  }  & (  )  & {  }  & WiCcMkAxs  & {  }  & TZzWxE  & [  ]   ^ "wDLLYoy"  ^ (  )  & PBjGoobzH  & [  ]   & "Jih"  & [  ]   & {  }  & {  }  ^ opiG  & [  ]   & CnpFdS  & [  ]   & [  ]   & EEgTE  & "OZHA"  & {  }  & 257  | [  ]   & [  ]   & {  }  & [  ]   & (  )  & [  ]   & {  } , "tKCNJWuK"  ^ 42  ^ {  }  ^ -95  ^ {  }  & "yRMbARTmYQRdwwKMe"  & 4  & dMdHDNkpI  & (  )  & tlxlXp  & 4  & [  ]   & (  )  & [  ]   & -98  ^ (  )  & uvMeqD  & (  )  & "kPsMSnaB"  & 65  & [  ]   & "ApaO"  ^ kizHIHorj  & (  )  & "kNlcDqXEaKlGzLO"  & KRQhxF  & [  ]   & [  ]   & RlQxSCQ  & 8 , [  ]   & {  }  ^ (  )  ^ MEZmM  & (  )  & 22  & "BDZPKSOfxq"  & [  ]   ^ [  ]   ^ ""  & KRjLG  & [  ]   & {  }  & [  ]   & (  )  & (  )  & {  }  & [  ]   & 50  & {  }  ^ AdJKi  & [  ]   ^ XzSYsMUwd  ^ (  )  & TwBX  & jagNdpA  & 5  & "ULrvrcVRWuCVFQONGV"  & (  )  & "LXoMyxZrKmodDCs"  ^ {  }  & -91  & {  }  & [  ]   & pqvtSECKC  ^ ""  & (  )  & -24  ^ "JwZYyz"  & [  ]   & UBnoVxuII  & "SrVfFrBVnXPDIQZ"  | [  ]   ^ -130  ^ (  )  & (  )  ^ (  )  & {  }  & {  }  & [  ]   & RxWqBotEU  & FMk  & RketfFPTY  & 19  & [  ]   & XRDAhpIy  ^ "ef"  & ""  & -19  & {  }  & (  )  & (  )  & ""  & "dEOmsuFJFePOfHuB"  & "YyZnAowm"  ^ Ego  & (  )  & {  }  & -127  ^ "MydlMnOBWkAGpt"  & 0  & (  )  & (  )  & {  }  & 45  & "iJVCBtyTVEeejLZ"  & [  ]   & "hYPbYMpfBPpLVBFHLdxQJQfyQNkMIDXbbOkFLlabhnj"  ^ (  )  | {  }  & [  ]   & "IwUmYS"  & {  }  & "mTHJuNP"  & (  )  & 256  & {  }  & [  ]   & (  )  & qAxY  ^ 9  ^ {  }  & (  )  & "vYhjGpEDJ"  & {  }  & {  }  ^ [  ]   & HmMbXY  & -128  & [  ]   & Mebq  & ""  & (  )  & (  )  & {  }  ^ {  }  & "xvwaVuvhdpDCEnKbmh"  & "lEu"  & [  ]   ^ lQYFO  ^ (  )  ^ jGgvMiQHv  ^ {  }  & (  )  & (  )  & (  )  & (  )  & [  ]   & "E"  & [  ]   & {  }  ^ WUOsqIzq  ^ "C"  & 88  & "hr"  & {  }  & -84  & Isjy  & [  ]   & [  ]   & "ymkcZWrtxfqqIFCosE"  & (  )  & rIEo , "aaYNCewAwJHlzsK"  ^ {  }  ^ "CeiyiEeQYH"  ^ 41  & 42  & {  }  & (  )  & {  }  & -79  & (  )  | AaRjO  & "YHtcZPOHhhpczNGEgV"  & [  ]   & (  )  & 257  & [  ]   & {  }  & 82  & [  ]   & GqYoqKg  ^ "cgU"  & (  )  & "ZIyCYksumlE"  & -12  & {  }  & NpVK  & -97  & [  ]   & [  ]   ^ (  )  & "wPDOuTDoSnK"  ^ -255  ^ 65  & (  )  & yTKVaQLhk  ^ CrFKefu  & 0  & JZzWXxy  & afdb  & [  ]   & "VAbg"  & "uvWLrLbzoDH"  & (  )  & ynGfv  ^ 76  & 59  & (  )  & "WpQtyhKE"  & [  ]   | [  ]   & [  ]   & (  )  | {  }  | "HlbcTlFqHjac"  & {  }  & 98  & 59  & aFBFpUuq  | (  )  & [  ]   & (  )  & (  )  & lmuCi  & {  }  & {  }  ^ GkKikgF  | [  ]   & "cn"  & [  ]   & [  ]   & "MpWvzKiPen"  & (  )  | -257 , {  }  & OPzBcnD  & AMMHeIBSK  & (  )  & FGeaUGjQw  & MZagQrYOb  & "Ultv"  & [  ]   | {  }  & GnBTGaH  & {  }  & FEpIFcpN  ^ {  }  & (  )  & 22  & 81  ^ {  }  & ""  & {  }  & 0  | VGJ  ^ (  )  ^ (  )  & 38  & [  ]   & "wKltJKNywKvY"  & xUDNwGBq  & {  }  & (  )  & ""  & {  }  & {  }  ^ {  }  & [  ]   & "UkyMXawDGLsad"  & (  )  & (  )  & (  )  ^ [  ]   ^ -258  & [  ]   & JfhkFpC  & 255  & [  ]   & {  }  & -15  & {  }  & [  ]   & 67  ^ {  }  & {  }  & HaOlG  & ""  & 257  & (  )  & (  )  & EwxQvXt  & [  ]   & {  }  & [  ]   ^ {  }  & "B"  & "xJ"  & "bca"  & {  }  & "qpligzwo"  & [  ]   & ITklmd  ^ "k"  & [  ]   & vXCQLgIrx  & (  )  & [  ]   & -45  & -13  & yKjAEjCH  ^ (  )  | [  ]   ^ YtXuEdVq  & [  ]   & "EHnVss"  ^ {  }  ^ VjT  ^ "KwhQRD"  ^ 90  | YoR  ^ -22  & -4  & {  }  & {  }  & [  ]   & "QbceuESiGAeglRu"  & "mTUsPVcD"  & tJVvZG  & {  }  ^ 64  ^ {  }  & (  )  & "XUsrserHBUsttgP"  & 54  & [  ]   & HMi  & -58  & -258  & {  }  & 8  & [  ]   ^ -22  & 7  & 20  & {  }  & (  )  ^ 0  & {  }  & 16  & yJXMcb  & iLNQaHOp  & (  )  & LHkG  & [  ]   & [  ]   & (  )  & {  } , "LOXJBtxKYSZQIpMDT"  ^ "CEVAsVaTlDaJMce"  & -13  & [  ]   & {  }  & {  }  & [  ]   & iEmJOQV  & {  }  ^ "KygenoQnPxbqFmI"  ^ EdRAPNy  & nNT  & AuFV  ^ [  ]   & [  ]   & -2  & [  ]   & "tfR"  & {  }  & nqCbsLpJ  & 22  & {  }  ^ -47 , ; global Wqf, oquODI, MqfM, jXlA; exec (  )  ^ ""  << (  )  >> {  }  & "SwJRjCof"  >> {  }  << -90  >> {  }  >> [  ]   >> 45  << (  )  >> "kBpb"  << (  )  & lmxS  ^ {  }  ^ {  }  & [  ]   & {  }  & zma  & [  ]   << (  )  << kNXG  >> VBnCPJxt  >> {  }  >> "xuoRzlNJo"  << "pSlHpIaVY"  & (  )  ^ [  ]   & "i"  & (  )  & Fziwif  & [  ]   & (  )  & 44  >> aZODcpNwH  >> -128  & {  }  & (  )  << (  )  << {  }  << -94  & ""  ^ ClDfv  | {  }  >> 91  << -86  << "HmPQkaPJ"  << "vxHvtFgJopAComixixf"  << {  }  >> (  )  ^ {  }  << {  }  >> 53  << (  )  & kygod  & {  }  << -80  << (  )  << "zmOqnxeOXUx"  << -30  >> (  )  << nURd  << (  )  << bcBltS  >> "DyLgh"  << "lJNbXfOgP"  & {  }  >> 7  << jLReBbFLy  << 37  >> (  )  << (  )  >> 6  << rwSsFVn  << {  }  >> [  ]   << [  ]   & (  )  & "XpmIx"  & LYBsJEfD  & {  }  << {  }  >> 0  & 41  ^ -22  >> [  ]   << "H"  << {  }  >> AUGPD  >> [  ]   << WgFVu  >> (  )  & fjbRTsP  ^ (  )  ^ (  )  & {  }  << (  )  >> 74  >> JgzaChUEF  >> [  ]   >> 40  >> {  }  << [  ]   << [  ]   << (  )  & (  )  & [  ]   & -31  & {  }  << xAl  << (  )  << HRLWpr  >> ""  >> "OgqgemfajcyQP"  << [  ]   >> {  }  << (  )  << HCYulqJE  >> "BghIBYsvAFkhyyWkG"  ^ [  ]   & (  )  >> "AAcgvwQdhDpcYMq"  >> (  )  << "KWKQyuSfTOpLBulRuomNqtJEhMrlqnnPNl"  << [  ]   >> [  ]   >> PzNthqri  << 84  & ""  << (  )  >> -257  << jlXYnn  >> [  ]   << "N"  >> (  )  & (  )  << "KjRwBiT"  << mQB  ^ {  }  & -257  >> fulCTkfwi  << WzZQlhiNW  >> [  ]   >> [  ]   & 77  << "LairqvfEKLuW"  & {  }  & [  ]   >> {  }  >> -91  & (  )  >> [  ]   ^ aac  >> bkiKW  >> 14  << (  )  >> bJll  >> [  ]   << lNJ  & {  }  << [  ]   << "jLOQLhLMA"  << MsrLbdZd  & (  )  & (  )  >> (  )  << (  )  >> -258  >> {  }  & ""  >> [  ]   >> -1  << {  }  >> "ijqOtdJjIRRqmOMp"  >> {  }  << "upLcIbNzOgXUzFqiqY"  >> (  )  & (  )  & [  ]   ^ (  )  & {  }  & "R"  & "nRiUvaQAqqf"  << "r"  << -99  << {  }  >> (  )  >> [  ]   << [  ]   >> -20  & [  ]   ^ {  }  << 22  >> SRR  << "bZ"  << "eqCvsZWTWDKqzEWc"  << ldt  >> ooFcE  << MYrOWu  << ETAddIA  >> {  }  & "l"  & "Yq"  & 77  & (  )  >> "uxOlpHhk"  & [  ]   & {  }  >> {  }  << [  ]   << [  ]   & [  ]   | xDhdlrCt  & (  )  << (  )  >> "JaDjknm"  >> {  }  & XivsUc  >> [  ]   << {  }  >> [  ]   >> "IhMlWBkz"  >> (  )  >> DMc  & pglKpJcPR  << "oWxsRAZLzT"  >> bLrRBzX  << (  )  >> [  ]   & 37  << {  }  >> (  )  << "e"  >> (  )  >> {  }  << "brBmBo"  << {  }  >> 58  >> (  )  & 71  >> [  ]   << "D"  << "SeVYZayMqMWT"  << (  )  << (  )  << 66  << (  )  & FCphPtB  & [  ]   >> -255  << "SiWKvgnlvLYg"  >> 12  >> (  )  >> {  }  >> jhLJaRJP  << {  }  & yHq  & [  ]   >> Kujh  >> (  )  << YwPGa  ^ "OLbiCi"  >> "faVhcLCrX"  >> (  )  >> {  }  >> LChSMu  << OkuVtQf  << [  ]   >> (  )  ^ (  )  ^ (  )  >> (  )  << 93  >> {  }  << "ITMoTS"  >> (  )  >> "fgsQzrmdBKMlvQMj"  & -6  & (  )  & (  )  << (  )  >> [  ]   >> (  )  & ""  ^ ouQswG  ^ "pblpPbKRUZMijmGpoHF"  ^ "EprmScSgGtEIPCFJBI"  ^ "hWQNTuAvtiyDZe"  >> [  ]   >> (  )  >> [  ]   >> XHxA  >> "GTaDYtbMh"  << lkELQCytE  & 26  >> [  ]   >> {  }  >> 7  & (  )  & "pmADfSAC"  >> {  }  << 256  << {  }  << -257  >> 126  >> [  ]   >> -82  >> [  ]   & "MxZRGneSkdn"  << 6  << (  )  & [  ]   ^ -59  ^ (  )  << {  }  >> WLtNsqP  << [  ]   << {  }  << DAoX  << -59  << (  )  ^ [  ]   & (  )  << QdCY  >> [  ]   >> (  )  << (  )  << -129  << xxAzIZq  & [  ]   << {  }  << [  ]   << (  )  >> (  )  << [  ]   << "UsRJpdAhfOe"  >> (  )  & [  ]   & lvYIv ; pass; assert (  )  or {  }  or "hFikafOZJqrzdREYZA"  or not [  ]   or not [  ]   and [  ]   and not {  }  or (  )  and not {  }  or {  }  and {  }  or not -127  or WsmJeSyl  and 75  and NPOh  or not "oJSqCfwLVOmcUr"  and not -55  and -59  and not (  )  and not Zxhq  and "SjhpBTibUwmTI"  and {  }  and not "YdasoXOmIoUQXQoZ"  if [  ]   and {  }  and not {  }  else lambda : 56  if "u"  else {  } ; continue; print lambda : lambda **TomxFHip: "z" ; print  >> lambda (HmM), aUk, flgsoLdGr=[  ]   if uUSec  else 36 , DdyLpQj, : lambda : hrpaioqha , lambda **HmxMDOJkY: -7  or (  )  or {  }  or (  )  or caX  or (  )  or (  )  or SuKYfcRG  or {  }  or {  }  if [  ]   or (  )  or "TZV"  or 80  or rgUDU  or "CIzXaAhZBOBIxwiR"  or {  }  or {  }  or 128  or "yalIRzFk"  else IxIPOA  if [  ]   else 38 , (  )  and not 126  and not 59 , not 74  or not -69  if not "FQzCIJgVJzBS"  and not {  }  and not (  )  and not {  }  and [  ]   and {  }  and {  }  or (  )  and "A"  and not 40  and not {  }  or not (  )  and not 71  or not [  ]   and not (  )  and not tuoqpbfgb  and not VzFSsrU  and [  ]   and "tIyMIcXLFtcInpDm"  and (  )  or not -79  and not {  }  and "qNaZOgzsDEgo"  and {  }  and {  }  and not (  )  or FuSU  or {  }  or not 71  and not [  ]   and 1  and [  ]   and (  )  and [  ]   or [  ]   and not {  }  else lambda : lambda : -27 , lambda : lambda : -31 , lambda : lambda **eMu: {  } , ; print not -4  or PsnNVW  or eGEy  or not rbGeSGA  and not wgCpSTjiQ  and not KjBkmETm  and {  }  or not "yapPVdV" ; del [  ]   & -2  & {  }  & WOEVih  & (  )  & -15  & "dV"  & (  )  ^ "gIohKxLLrBel"  & QUgufsYU  & "W"  & {  }  & "uJ"  & (  )  & 7  & {  }  ^ [  ]   ^ {  }  ^ -17  & 63  & [  ]   & -258  & (  )  & 51  & aLmhxk  & [  ]   & (  )  ^ [  ]   & fxE  & (  )  & -66  & -19  & dJqukWRwA  & 79  ^ -256  & 71  & (  )  & [  ]   & "lqBxCcbTOQ"  & RiYggrYZ  & {  }  & [  ]   ^ [  ]   & "Cc"  & "tueOJoC"  & [  ]   ^ [  ]   & (  )  & -83  & LmVnk  & (  )  & [  ]   & {  }  & (  ) ; break
class fttLKcPo():pass; assert {  }  if VUAA  else [  ]  , lambda : [  ]
global mBzFud
print  >> lambda : "g" , not WhhgLXm  and not ojmQTtk  and {  }  and -26  and not {  }  and not (  )  and not 127  and (  )  and not NGYWuwIBr ; print  >> lambda : [  ]   if ruT  else lambda : [  ]  , lambda (rjAbWV), **nMyD: "i" , not [  ]   or (  )  or not (  )  or IMg  and not {  }  and "BJqmCDMmMXFoXs"  and reZFI  and not 84  and [  ]   and (  )  and "m"  and not [  ]   and (  )  and [  ]   or not "JotDypIXi"  or MgTlCeZO  or not ""  or {  }  or {  }  or not (  )  or not [  ]   and [  ]   and [  ]   if not (  )  and [  ]   and sjUEksgnb  and not LGNLGj  and {  }  and (  )  and jDQXKX  and not (  )  and not gmtr  and not 20  and "UXijK"  else {  }  and (  )  and (  )  and (  )  and (  )  and "FBFizHZBDCb"  and 69  and [  ]   and fjchdhL  and "rB"  or -127  and 92  and {  }  and "iMJE"  and "eKEuupg"  and [  ]   and lfc  or {  }  and -78  and 27  and (  )  and (  )  and (  )  or [  ]   and {  }  and (  )  and [  ]   and [  ]   and {  } ; continue; print lambda *xPhpPILS: (  )  or {  }  or "JyVNDaNqrJGhwRclzD"  or iTMJrQ  or -54  or {  }  or (  )  or (  )  or [  ]   or -2 , not KeFTn  or not (  )  and (  )  and (  )  or not "TRhiKZsOAJNciijOftPFqGMORBJHFLntBHFtxHEfwNyVgRrOobFOIvAenOBFBhCULnXlggcPGDAcJmGaPg"  and "mIIDLhNjDFoBbHIa"  and [  ]   or "jtwXJoqLchj"  and 48  or {  }  if [  ]   and {  }  and not "PnAUNJnbYnlnYpQFXXL"  and 254  and not 56  and not [  ]   and [  ]   and not (  )  else [  ]   or {  }  or "m"  or ""  and fOs  and {  }  and (  )  and DCUV  and [  ]   and 99  and -52  and [  ]   and [  ]   or [  ]   and {  }  and "uPigZXjwLMWo"  and 1  and {  }  and SHHYTZJWl  and "r"  and (  )  and -39  if {  }  and {  }  and 73  and -129  and -67  and {  }  and -36  and -8  and BodaoPLl  or (  )  else (  )  or "UfMjuVAtjPAyJXej"  or {  }  or {  }  or (  )  or 255  or "WYpPhnidKMULQIk"  or 14  or (  )  if "BOxzgIwAgvcY"  else [  ]  , lambda (aJOnBg), (qPBVtFYEh)="H" , (RWe)=(  )  if RHZPb  else "QKOgsaoFtKgvFU" , QEhEr, (lfN), bkfGzg, (WCcTAWY), gNecl=[  ]  , (AeojLQ)={  } , (LSKShxIs)=lambda : [  ]  , (NQrhTL)=rFvnRfPA  if RRod  else -70 , : lambda : "PRHWinemBZoypdHvlcb" , ; assert not [  ]   and (  )  and not {  }  and {  }  and [  ]   and not "WJNMsNqCTtMtrTFma"  or [  ]   and (  )  and not [  ]   and "IcGIyUIbnut"  and "KSnQeACzzIuDGa"  or "uvNbWYyalRTpwvJsJ"  or not "ydMnQrDeYAgSwZv"  and [  ]   and "eS"  and "kgXsrpZEouYlWu"  and not {  }  and [  ]   and {  }  and "f"  or 254  and not (  )  or -14  or not -54  and not 255  and [  ]   and "qIhSTBqwSQYOrC"  and not {  } , lambda (ckM), KaKbS, OamgVCjE, DDcQz=lambda : XvFEmltPD , (znBcBdPr)="NvlF" , mlYIjCb=lambda : lhest , (cXpTC), vhSCYu={  } , (lMpINf)=lambda : (  ) , dQu=lambda : "ogjVExLuxVxlEb" , : (  )  or IYuIkg  or [  ]   or [  ]   or {  }  or 79  or ""  or "NBpMOgiTBGDplqbSUEjXWwwdXJvpAxLNkcRbCsFNChrEhUbVRZPboWkHQFKapUrlTogsXfXSKsyVsCemxaAVUjSYwwcHueZPgft"  or -257  or "fpVwDiF"  if [  ]   else lambda : (  ) ; from Pcajs.YDMq.oSl import nxk as AXYYfvpqD, bfC as EsEGjphz, SXyNHRBX, OQVGsLOt, eycrWMwjU as Twknnx, Pwe, MJHT, iyn as vwe, ; assert lambda : VLS  or "i"  or "AeeQtcfuwzEhOjVMnOW"  or (  )  or {  }  or "B"  or hXDKBYnU  or [  ]   or 68  if "dWbhgbYgUoCAR"  or [  ]   or (  )  or (  )  or [  ]   else (  )  if {  }  else (  ) , "cvLUKBVirgqdulavsi"  and not fUI  and not [  ]   and (  )  and (  )  or (  )  or not (  )  or not 42  or not -58  if not ""  else lambda **xgJ: lambda : (  )
def NVytX((hawZR, (xasSMmTV), )):
@REabCl
@SvzfucguG
@JRulG
@KwGnSWWQ
def xdRNgHqrs():pass
raise
try:
pass
pass
pass

except 55 , (  ) :
pass
pass
pass
pass
pass

except [  ]   as -84 :pass
except "bnAxZuxBaFNevQVZHghdwyTucBzWCLppaAOukJeakXhbkEbGkqKcZtFadMNTQZVAqmCssXMqBrkAe" , [  ]  :pass
except {  } , [  ]  :
pass
pass
pass
pass
pass
pass
pass

except nlS  as 53 :
pass
pass
pass
pass
pass
pass
pass

except {  } , jbaKMlK :pass
else:
pass


#### Reference Depth: 15

\$> python examples/example.py -g python27 -n 1 -s 1337 --max-recursion 15