From 6ff517a8e4227d9489c7b771984dda7508a8158b Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Fri, 3 Jul 2015 17:24:29 +0200 Subject: Improved parser --- Logic.dcl | 1 + Logic.icl | 3 +++ LogicParser.icl | 7 +++++-- README.md | 48 ++++++++++++++++++++++++++++++++++++++++++++++-- 4 files changed, 55 insertions(+), 4 deletions(-) diff --git a/Logic.dcl b/Logic.dcl index 7e50822..1a0821b 100644 --- a/Logic.dcl +++ b/Logic.dcl @@ -85,6 +85,7 @@ subexprs :: Expr -> [Expr] // Subexpressions of an expression sorted_subexprs :: (Expr -> [Expr]) // Similar, but roughly sorted by complexity simple_truthtable :: Expr -> TruthTable // Simple truthtable: only the atomic expression and the expression itself +simple_truthtable_n :: [Expr] -> TruthTable // Simple truthtable with multiple expressions truthtable :: Expr -> TruthTable // Truthtable from an expression parse :: String -> Expr // Parse a string into an expression diff --git a/Logic.icl b/Logic.icl index 0d739cd..dabc71d 100644 --- a/Logic.icl +++ b/Logic.icl @@ -250,6 +250,9 @@ sorted_subexprs = sort o subexprs simple_truthtable :: Expr -> TruthTable simple_truthtable e = {exprs = [Atom a \\ a <- all_atoms e] ++ [e], options = all_atom_options e} +simple_truthtable_n :: [Expr] -> TruthTable // Simple truthtable with multiple expressions +simple_truthtable_n es = {exprs = removeDup ([Atom a \\ a <- flatten (map all_atoms es)] ++ es), options = flatten (map all_atom_options es)} + truthtable :: Expr -> TruthTable truthtable e = {exprs = sorted_subexprs e ++ [e], options = all_atom_options e} diff --git a/LogicParser.icl b/LogicParser.icl index b25b0e5..320e2cc 100644 --- a/LogicParser.icl +++ b/LogicParser.icl @@ -26,9 +26,12 @@ module LogicParser import StdEnv, StdMaybe, ArgEnv, Logic Start -| argc <> 1 = abort ("Usage: " +++ argv.[0] +++ " -b -nt \n") -| otherwise = toString (truthtable (parse argv.[1])) +| argc < 1 = abort ("Usage: " +++ argv.[0] +++ " -b -nt \n") +| extended = toString (truthtable (parse argv.[2])) +| otherwise = toString (simple_truthtable_n [parse argv.[n] \\ n <- [1..argc]]) +//| otherwise = toString ((if extended truthtable simple_truthtable) (parse argv.[1])) where argc = size argv - 1 argv = getCommandLine + extended = argv.[1] == "-e" diff --git a/README.md b/README.md index dc01fb5..0d2c3f6 100644 --- a/README.md +++ b/README.md @@ -15,9 +15,17 @@ Read further for examples. ### Operators -There is one unary operator (`Op1`): `Not`. +There is one unary operator (`Op1`): `Not`. It binds stronger than all other operators. -There are four binary operators (`Op2`): `And`, `Or`, `Impl` and `Equiv`. `And` is considered left-associative; all others are considered right-associative. Associativity is only important in `toString` functions. `Expr` itself is an unambiguous recursive type. +There are four binary operators (`Op2`). In order of descending precedence: `And`, `Or`, `Impl` and `Equiv`. `And` is considered left-associative; all others are considered right-associative. Associativity is only important in `toString` functions. `Expr` itself is an unambiguous recursive type. + +The operators are represented as: + + * Not: `~` + * And: `&` + * Or: `|` + * Impl: `->` + * Equiv: `<->` ### Expressions @@ -95,12 +103,48 @@ The `truthtable` of `e15`: True | True | False | False | False True | True | True | True | True +## Parsing + +The `parse` function may be used to read an expression from a String. The following rules are used: + + * Whitespace is ignored. + * All latin letters (`[a-zA-Z]`) are considered atomic expressions + * Operators are expected in their representation described above + * True and False are expected as `1` and `0`, respectively + +A usage example is found in `LogicParser.icl`. This file, once compiled, reads the command line arguments and shows their truth tables: + + $./LogicParser -b -nt -e "~~(((A | (A -> B)) -> B) -> B)" + A | B | A -> B | A | (A -> B) | A | (A -> B) -> B | (A | (A -> B) -> B) -> B | ~((A | (A -> B) -> B) -> B) | ~~((A | (A -> B) -> B) -> B) + -------+-------+--------+--------------+-------------------+--------------------------+-----------------------------+------------------------------ + False | False | True | True | False | True | False | True + False | True | True | True | True | True | False | True + True | False | False | True | False | True | False | True + True | True | True | True | True | True | False | True + +Here, `-b` and `-nt` are common Clean options to disable outputting basic values for constructors, and disable outputting execution times, respectively. + +The option `-e` tells the parser to show the extended truth table. With this option, only the first formula is considered. Without `-e`, multiple formulas may be given (possibly with different atomic expressions), and all will be evaluated in one table: + + $./LogicParser -b -nt "~~(((A | (A -> B)) -> B) -> B)" "A & B" + A | B | ~~((A | (A -> B) -> B) -> B) | A & B + -------+-------+------------------------------+------- + False | False | True | False + False | True | True | False + True | False | True | False + True | True | True | True + False | False | True | False + False | True | True | False + True | False | True | False + True | True | True | True + ## Future ideas * Different `toString` formats for operators: HTML (`¬`), UTF-8 (¬), LaTeX (`\neg`) * Different `toString` formats for booleans: `0` and `1` or `T` and `F` instead of `True` and `False` * Simplifying expressions with atomic expressions as far as possible * Testing equivalence or impliance of expressions with atomic expressions + * Add support for multi-letter atomic expressions ## License -- cgit v1.2.3