Zack Williams | 28f1e49 | 2019-02-01 10:02:56 -0700 | [diff] [blame] | 1 | from __future__ import absolute_import |
| 2 | from __future__ import print_function |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 3 | __author__ = "Sapan Bhatia" |
| 4 | |
| 5 | __copyright__ = "Copyright (C) 2017 Open Networking Lab" |
| 6 | __version__ = "1.0" |
| 7 | |
Scott Baker | 20997cf | 2019-04-04 10:10:06 -0700 | [diff] [blame^] | 8 | import sys |
Zack Williams | 28f1e49 | 2019-02-01 10:02:56 -0700 | [diff] [blame] | 9 | from .helpers import LexHelper |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 10 | |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 11 | |
Sapan Bhatia | 9c57972 | 2018-01-12 13:45:09 -0500 | [diff] [blame] | 12 | class FOLParsingError(Exception): |
Zack Williams | be7f36d | 2018-02-02 11:37:11 -0700 | [diff] [blame] | 13 | |
Sapan Bhatia | 9c57972 | 2018-01-12 13:45:09 -0500 | [diff] [blame] | 14 | def __init__(self, message, error_range): |
| 15 | super(FOLParsingError, self).__init__(message) |
| 16 | self.error_range = error_range |
| 17 | |
Zack Williams | be7f36d | 2018-02-02 11:37:11 -0700 | [diff] [blame] | 18 | |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 19 | class FOLLexer(object): |
Sapan Bhatia | cee0402 | 2017-07-20 02:12:43 -0400 | [diff] [blame] | 20 | keywords = ('forall', 'exists', 'True', 'False', 'not', 'in') |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 21 | |
Zack Williams | be7f36d | 2018-02-02 11:37:11 -0700 | [diff] [blame] | 22 | tokens = ['STRING_LITERAL', |
| 23 | 'NUM', |
| 24 | 'ESCAPE', |
| 25 | 'COLON', |
| 26 | 'IMPLIES', |
| 27 | 'OR', |
| 28 | 'AND', |
| 29 | 'LPAREN', |
| 30 | 'RPAREN', |
| 31 | 'EQUALS', |
| 32 | 'SYMBOL', |
| 33 | 'LT', |
| 34 | 'RT', |
| 35 | 'STAR'] + [k.upper() for k in keywords] |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 36 | # literals = '()+-*/=?:,.^|&~!=[]{};<>@%' |
| 37 | |
| 38 | t_ignore_LINE_COMMENT = '//.*' |
| 39 | t_COLON = '\\:' |
| 40 | t_IMPLIES = '\\-\\>' |
| 41 | t_OR = '\\|' |
Sapan Bhatia | 9966973 | 2017-07-25 19:19:14 -0400 | [diff] [blame] | 42 | t_STAR = '\\*' |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 43 | t_LT = '\\<' |
| 44 | t_RT = '\\>' |
| 45 | t_AND = '\\&' |
| 46 | t_LPAREN = '\\(' |
| 47 | t_RPAREN = '\\)' |
Sapan Bhatia | fc1278c | 2017-07-17 12:57:13 -0400 | [diff] [blame] | 48 | t_NUM = r'[+-]?\d+(\.\d+)?' |
| 49 | t_STRING_LITERAL = r'\"([^\\\n]|(\\.))*?\"' |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 50 | |
| 51 | t_EQUALS = '\\=' |
| 52 | |
| 53 | literals = '()+-*/=?:,.^|&~!=[]{};<>@%' |
| 54 | |
| 55 | t_ignore = ' \t\f' |
| 56 | |
| 57 | def t_newline(self, t): |
| 58 | r'\n+' |
| 59 | t.lexer.lineno += len(t.value) |
| 60 | |
| 61 | def t_newline2(self, t): |
| 62 | r'(\r\n)+' |
| 63 | t.lexer.lineno += len(t.value) / 2 |
| 64 | |
Sapan Bhatia | 9c57972 | 2018-01-12 13:45:09 -0500 | [diff] [blame] | 65 | def t_ESCAPE(self, t): |
| 66 | r'{{ (.|\n)*? }}' |
| 67 | t.lexer.lineno += t.value.count('\n') |
| 68 | return t |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 69 | |
| 70 | def t_BLOCK_COMMENT(self, t): |
| 71 | r'/\*(.|\n)*?\*/' |
| 72 | t.lexer.lineno += t.value.count('\n') |
| 73 | |
| 74 | def t_SYMBOL(self, t): |
Zack Williams | 28f1e49 | 2019-02-01 10:02:56 -0700 | [diff] [blame] | 75 | r'[A-Za-z_$][\.A-Za-z0-9_+$]*(\(\))?' |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 76 | if t.value in FOLLexer.keywords: |
| 77 | t.type = t.value.upper() |
| 78 | return t |
| 79 | |
| 80 | def t_error(self, t): |
Zack Williams | 28f1e49 | 2019-02-01 10:02:56 -0700 | [diff] [blame] | 81 | print(("Illegal character '{}' ({}) in line {}".format( |
Scott Baker | 20997cf | 2019-04-04 10:10:06 -0700 | [diff] [blame^] | 82 | t.value[0], hex(ord(t.value[0])), t.lexer.lineno)), |
| 83 | file=sys.stderr) |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 84 | t.lexer.skip(1) |
Zack Williams | be7f36d | 2018-02-02 11:37:11 -0700 | [diff] [blame] | 85 | |
| 86 | |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 87 | class FOLParser(object): |
| 88 | tokens = FOLLexer.tokens |
| 89 | offset = 0 |
| 90 | lh = LexHelper() |
| 91 | |
| 92 | def setOffset(self, of): |
| 93 | self.offset = of |
| 94 | self.lh.offset = of |
| 95 | |
Sapan Bhatia | fc1278c | 2017-07-17 12:57:13 -0400 | [diff] [blame] | 96 | def p_term_numeric_constant(self, p): |
| 97 | '''term : NUM''' |
| 98 | p[0] = p[1] |
| 99 | |
| 100 | def p_term_string_constant(self, p): |
| 101 | '''term : STRING_LITERAL''' |
| 102 | p[0] = p[1] |
| 103 | |
| 104 | def p_term_boolean_constant(self, p): |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 105 | '''term : FALSE |
| 106 | | TRUE''' |
| 107 | p[0] = p[1] |
| 108 | |
Sapan Bhatia | 9966973 | 2017-07-25 19:19:14 -0400 | [diff] [blame] | 109 | def p_term_policy_function(self, p): |
| 110 | '''term : STAR SYMBOL LPAREN SYMBOL RPAREN''' |
| 111 | p[0] = {'policy': [p[2], p[4]]} |
| 112 | |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 113 | def p_fole_not(self, p): |
| 114 | '''fole : NOT fole''' |
| 115 | p[0] = {p[1]: p[2]} |
| 116 | |
| 117 | def p_fole_term(self, p): |
| 118 | '''fole : term''' |
| 119 | p[0] = p[1] |
| 120 | |
| 121 | def p_term_symbol(self, p): |
| 122 | '''term : SYMBOL''' |
| 123 | p[0] = p[1] |
| 124 | |
| 125 | def p_term_python(self, p): |
Sapan Bhatia | b934f72 | 2017-07-15 08:42:19 -0400 | [diff] [blame] | 126 | '''term : ESCAPE''' |
Sapan Bhatia | bc6268c | 2017-07-16 02:43:45 -0400 | [diff] [blame] | 127 | p[0] = {'python': p[1].lstrip('{ ').rstrip(' }')} |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 128 | |
| 129 | def p_fole_group(self, p): |
| 130 | "fole : LPAREN fole RPAREN" |
| 131 | p[0] = p[2] |
| 132 | |
Sapan Bhatia | cee0402 | 2017-07-20 02:12:43 -0400 | [diff] [blame] | 133 | def p_fole_in(self, p): |
| 134 | "fole : term IN term" |
| 135 | p[0] = {'in': (p[1], p[3])} |
| 136 | |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 137 | def p_fole_equals(self, p): |
| 138 | "fole : term EQUALS term" |
| 139 | p[0] = {'=': (p[1], p[3])} |
| 140 | |
| 141 | def p_fole_binary(self, p): |
| 142 | '''fole : fole AND fole |
| 143 | | fole OR fole |
| 144 | | fole IMPLIES fole''' |
| 145 | p[0] = {p[2]: [p[1], p[3]]} |
| 146 | |
| 147 | def p_fole_quant(self, p): |
| 148 | '''fole : FORALL SYMBOL COLON fole |
| 149 | | EXISTS SYMBOL COLON fole''' |
| 150 | p[0] = {p[1]: [p[2], p[4]]} |
| 151 | |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 152 | def p_goal(self, p): |
| 153 | '''goal : LT fole RT''' |
| 154 | p[0] = p[2] |
| 155 | |
| 156 | def p_error(self, p): |
Sapan Bhatia | 9c57972 | 2018-01-12 13:45:09 -0500 | [diff] [blame] | 157 | error = 'error: {}'.format(p) |
Zack Williams | be7f36d | 2018-02-02 11:37:11 -0700 | [diff] [blame] | 158 | raise FOLParsingError(error, (p.lineno, p.lexpos, len(p.value))) |
Sapan Bhatia | 64c7251 | 2017-06-23 02:32:45 -0700 | [diff] [blame] | 159 | |
Sapan Bhatia | 9c57972 | 2018-01-12 13:45:09 -0500 | [diff] [blame] | 160 | precedence = ( |
Zack Williams | be7f36d | 2018-02-02 11:37:11 -0700 | [diff] [blame] | 161 | ("right", "IMPLIES"), |
| 162 | ("left", "OR"), |
| 163 | ("left", "AND"), |
| 164 | ("right", "COLON"), |
| 165 | ("right", "NOT"), |
| 166 | ("right", "STAR"), |
| 167 | ("right", "ESCAPE"), |
| 168 | ("nonassoc", "EQUALS", "IN")) |