Truth table: Difference between revisions
→{{header|jq}}
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 3,073:
T T F T
T T T T</pre>
=={{header|jq}}==
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq'''
This entry uses a PEG ([https://en.wikipedia.org/wiki/Parsing_expression_grammar Parsing Expression Grammar]) approach
to the task. In effect, a PEG grammar for logic expressions
is transcribed into a jq program for parsing and
evaluating the truth values of such expressions.
The PEG grammar for logic expressions used here is essentially as follows:
<pre>
expr = (primary '=>' primary) / e1
e1 = e2 (('or' / 'xor') e2)*
e2 = e3 ('and' e3)*
e3 = 'not'? primary
primary = Var / boolean / '(' expr ')'
boolean = 'true' / 'false'
</pre>
where Var is a string matching the regex ^[A-Z][a-zA-Z0-9]*$
Notice that this grammar binds '=>' most tightly, and uses `not` as a
prefix operator.
The PEG grammar above is transcribed and elaborated in the jq function
`expr` below. For details about this approach, see for example
[[Compiler/Verifying_syntax#jq]]. That entry also
contains the jq PEG library that is referenced
in the 'include' statement at the beginning of the
jq program shown below.
====Parsing====
<syntaxhighlight lang=jq>
include "peg"; # see [[Compiler/Verifying_syntax#Generic_PEG_Library]
def expr:
def Var : parse("[A-Z][a-zA-Z0-9]*");
def boolean : (literal("true") // literal("false"))
| .result[-1] |= fromjson;
def primary : ws
| (Var
// boolean
// box(q("(") | expr | q(")"))
)
| ws;
def e3 : ws | (box(literal("not") | primary) // primary);
def e2 : box(e3 | star(literal("and") | e3)) ;
def e1 : box(e2 | star((literal("or") // literal("xor")) | e2)) ;
def e0 : box(primary | literal("=>") | primary) // e1;
ws | e0 | ws;
def statement:
{remainder: .} | expr | eos;
</syntaxhighlight>
====Evaluation====
<syntaxhighlight lang=jq>
# Evaluate $Expr in the context of {A,B,....}
def eval($Expr):
if $Expr|type == "boolean" then $Expr
elif $Expr|type == "string" then getpath([$Expr])
elif $Expr|length == 1 then eval($Expr[0])
elif $Expr|(length == 2 and first == "not") then eval($Expr[-1])|not
elif $Expr|(length == 3 and .[1] == "or") then eval($Expr[0]) or eval($Expr[2])
elif $Expr|(length == 3 and .[1] == "xor")
then eval($Expr[0]) as $x
| eval($Expr[2]) as $y
| ($x and ($y|not)) or ($y and ($x|not))
elif $Expr|(length == 3 and .[1] == "and") then eval($Expr[0]) and eval($Expr[2])
elif $Expr|(length == 3 and .[1] == "=>") then (eval($Expr[0])|not) or eval($Expr[2])
else $Expr | error
end;
</syntaxhighlight>
====Truth Tables====
<syntaxhighlight lang=jq>
# input: a list of strings
# output: a stream of objects representing all possible true/false combinations
# Each object has the keys specified in the input.
def vars2tf:
if length == 0 then {}
else .[0] as $k
| ({} | .[$k] = (true,false)) + (.[1:] | vars2tf)
end;
# If the input is a string, then echo it;
# otherwise emit T or F
def TF:
if type == "string" then .
elif . then "T"
else "F"
end;
# Extract the distinct variable names from the parse tree.
def vars: [.. | strings | select(test("^[A-Z]"))] | unique;
def underscore:
., (length * "_");
</syntaxhighlight>
====Examples====
<syntaxhighlight lang=jq>
def tests: [
"A xor B",
"notA",
"A and B",
"A and B or C",
"A=>(notB)",
"A=>(A => (B or A))",
"A xor B and C"
];
def tables:
tests[] as $test
| ($test | statement | .result)
| . as $result
| vars as $vars
| ($vars + [" ", $test] | join(" ") | underscore),
(($vars | vars2tf)
| ( [.[], " ", eval($result) | TF] | join(" ")) ),
""
;
tables
</syntaxhighlight>
{{output}}
<pre>
A B A xor B
_____________
T T F
F T T
T F T
F F F
A notA
________
T F
F T
A B A and B
_____________
T T T
F T F
T F F
F F F
A B C A and B or C
____________________
T T T T
F T T T
T F T T
F F T T
T T F T
F T F F
T F F F
F F F F
A B A=>(notB)
_______________
T T F
F T T
T F T
F F T
A B A=>(A => (B or A))
________________________
T T T
F T T
T F T
F F T
A B C A xor B and C
_____________________
T T T F
F T T T
T F T T
F F T F
T T F T
F T F F
T F F T
F F F F
</pre>
=={{header|Julia}}==
| |||