Add parser

diff --git a/.gitignore b/.gitignore
index 8d441565e8733ccb9b2e87b73ad7977df7a7983c..bf5a5a294c9c81218ea3251a7c037ab4c6246f29 100644 (file)
--- a/.gitignore
+++ b/.gitignore
@@ -1 +1,3 @@
 /*.py[co]
+/parser.out
+/parsetab.py

diff --git a/grammar b/grammar
new file mode 100644 (file)
index 0000000..7ded1c2
--- /dev/null
+++ b/grammar
@@ -0,0 +1,27 @@
+# Grammar rules for tag searching; BNF.
+
+# The grammar defines expressions in the following forms:
+#  TAG - search blog posts that contain the tag;
+#  !TAG - search blog posts that don't contain the tag;
+#  TAG & TAG - search blog posts that contain both tags;
+#  TAG | TAG - search blog posts that contain one of the tags or both;
+# Parentheses are allowed to group expressions:
+#  TAG & (TAG | TAG)
+#  !(TAG | TAG)
+# and so on. This  is the first version of the grammar and it allows
+# rather stupid expressions, like !!TAG or ((TAG)); in the future
+# it will be fixed by making the grammar stricter and more complex.
+
+NAME : '[a-z][a-z0-9_]+'
+
+AND_OP : '&'
+
+OR_OP : '|'
+
+NOT_OP : '!'
+
+expression : NAME
+           | expression AND_OP expression
+           | NOT_OP expression
+           | expression OR_OP expression
+           | '(' expression ')'

diff --git a/parse_query.py b/parse_query.py
index 4533413f783bd163efca15393822c4d38172cb0a..c74eb78d21a29a5d33ec85af523ed85266b41796 100644 (file)
--- a/parse_query.py
+++ b/parse_query.py
@@ -18,3 +18,35 @@ def t_error(t):
     """Avoid warnings on stderr"""
 
 lexer = lex.lex()
+
+def p_expression_name(p):
+    """expression : NAME"""
+    p[0] = ('NAME', p[1])
+
+def p_expression_and(p):
+    """expression : expression AND_OP expression"""
+    p[0] = ('AND', p[1], p[3])
+
+def p_expression_not(p):
+    """expression : NOT_OP expression"""
+    p[0] = ('NOT', p[2])
+
+def p_expression_or(p):
+    """expression : expression OR_OP expression"""
+    p[0] = ('OR', p[1], p[3])
+
+def p_expression_parens(p):
+    """expression : '(' expression ')'"""
+    p[0] = ('PARENS', p[2])
+
+def p_error(p):
+    """Avoid warnings on stderr"""
+    yacc.restart()
+
+precedence = (
+    ('left', 'OR_OP'),
+    ('left', 'AND_OP'),
+    ('right', 'NOT_OP'),
+)
+
+parser = yacc.yacc()

diff --git a/test_parser.py b/test_parser.py
new file mode 100755 (executable)
index 0000000..e8f213a
--- /dev/null
+++ b/test_parser.py
@@ -0,0 +1,31 @@
+#! /usr/bin/env python
+
+import unittest
+
+class TestParser(unittest.TestCase):
+    def test_01_import(self):
+        global parser
+        from parse_query import parser
+
+    def test_02_tag(self):
+        self.assertEqual(parser.parse('xxx'), ('NAME', 'xxx'))
+
+    def test_03_bad_tag(self):
+        from ply.lex import LexError
+        self.assertRaises(LexError, parser.parse, 'XXX')
+
+    def test_04_expression(self):
+        self.assertEqual(parser.parse('!(xxx&yyy)'),
+            ('NOT', ('PARENS', ('AND', ('NAME', 'xxx'), ('NAME', 'yyy'))))
+        )
+
+    def test_05_bad_expression(self):
+        self.assertIs(parser.parse('!(xxx&yyy'), None)
+
+    def test_06_expression2(self):
+        self.assertEqual(parser.parse('!xxx&yyy&zzz|ooo'),
+            ('OR', ('AND', ('AND', ('NOT', ('NAME', 'xxx')), ('NAME', 'yyy')), ('NAME', 'zzz')), ('NAME', 'ooo'))
+        )
+
+if __name__ == "__main__":
+    unittest.main()