A Note on Syntax of the PAC

Kuniaki Mukai

[2015/03/24] first draft
[2015/03/30] revised
[2017/04/27] minor updates

This note describes the syntax of the PAC of package 0.6.4, using BNF-like notations.

Contents

Section 1. PAC terms as nameless/anonymous predicates with globals.

Section 2. Functional expressions based on term completions

Section 3. Words as hybrid regular expressions in phrases

Section 4. Kind as conditional equations

Section 5. Glossary

/**

• pred * **/

Section 1. Pac Terms: Nameless Predicates

term --> prolog_term module_name --> prolog_module_name atom --> prolog_atom string --> prolog_string number --> prolog_number list --> prolog_list variable --> prolog_variable

atomic_term --> number | string | atom basic_callable_term --> atom | atom() | atom(term, ..., term) callable_term --> basic_callable_term | module_name: callable_term goal --> callable_term | (goal , goal) | (goal ; goal) | (goal -> goal) | if(goal, goal, goal) | if(goal, goal) | \+(goal) | module_name: goal

markup_rule --> (head ->> phrase)

pac_rule --> pac_rule_head | pac_rule_head :- goal

pac_rule_head --> list.

pac_pred --> pac_rule | pac_rule & pac_pred pac_term --> pred(global, pac_pred) | pred(pac_pred) | mrec([variable = pac_pred, ..., ]). | mrec(global, [variable = pac_pred, ..., ]). | rec(variable, global, pac_pred) | rec(variable, pac_pred) | global(global, pac_pred) | pac_pred | psf(goal) | psf(global, goal) | fun(pac_function) | \(list, exp) | fun(global, pac_function) | pipe(phrase) | pipe(global, phrase)

function_rule --> list -> exp

pac_function --> function_rule | function_rule & pac_function

Abbreviation on pred-terms.

abbreviation			normal form

====================== ======================== global(global, Cs) <==> pred(global, Cs) A1 & ... & An <==> pred([], A1 & ... & An) pred(X) <==> pred([], X). rec(F, X) <==> rec(F, [], X). \(X, E) <==> fun(X, E) fun(Funs) <==> fun([],Funs) fun(global, Funs) <==> pred(global, pac_pred), provided that pac_pred is obtained from Funs by expanding Funs. \(X, E) <==> fun([], X->E) X->E <==> fun([], X->E) psf(E) <==> psf([],E) psf(global, E) <==> pred(global, [X,Y]:- G) provided that

dummy --> E

is 'dcg_rule_translated' to

dummy(X, Y) :- G.

'sf' of psf stands for Sentential Form from formal language theory.

meta_arg --> variable | string | callable_term | pac_term | comma_list_of_meta_arg | module_name: meta_arg

/*

• exp * */

Section 2. Functional Expressions

canonical_exp --> number | string | [_|_]

Remark : the empty list [] is not a canonical_exp.

exp --> variable | canonical_exp | pac_term | @(exp, exp) | ::(kind, exp) | :: | @(exp) | @@(exp) | quote(exp) | `(exp) | #(exp) | :(exp) | module_name:exp | flip(pac_rule) | flip(numlist, pac_rule) | flip(function_rule) | flip(index_list, function_rule) basic_exp --> variable | canonical_exp | pac_term | @(exp, exp)

/**

• word * **/

Section 3. Words: Regular Expression in Phrases

phrase --> list | callable_term | word_term | extra_condition | (phrase, phrase) | (phrase; phrase) | (phrase -> phrase)

extra_condition --> { goal }

% word_term --> w(word) | w(word, A) | w(word, A, B) | wl(word) | wl(word, A) | wl(word, A, B)

where A and B are a list expression representing a difference list such that <word> matches a prefix of the input codes.

word --> regex_string | [] | . | atom | number | char(i_character_class) | word + word | word | word | word \ word | word & word | + word | * word | \+ word | \ word | ? word | word ^ (>=(positive_integer)) | word ^ (positive_integer - positive_integer) | word ^ (=<(positive_integer)) | word ^ positive_integer | rev(word) | special(atom, interval_list) | @(macro_name).

macro_name --> atom.

Remark. \( positive_integer \) is not supported.

regex_string --> " regex "

regex --> character_class regex --> regex regex regex --> regex | regex regex --> regex & regex regex --> (regex) regex --> regex {positive_integer, positive_integer} regex --> regex {positive_integer,} regex --> regex * regex --> regex + regex --> regex ? regex --> regex !

/***

• character_class * ***/

character --> basic_character | escape_symbol basic_character

escape_symbol --> \

Remark: A basic character is defined in PAC to be what swi-prolog gives it an internal code.

character_class --> character character_class --> [interval_list] | [^interval_list]

interval_list --> interval interval_list --> interval interval_list

interval --> character | character - character integer_interval --> integer | integer-integer | inf-integer | integer-sup | inf-sup

/***

• i_character_class * ***/

i_point --> character | integer i_interval --> i_point | { i_point | inf } - { i_point | sup }

i_interval_list --> [i_interval, ... , i_interval].

i_character_class --> i(i_interval) | i(i_interval_list) | i_character_class '|' i_character_class | i_character_class & i_character_class | out(i_character_class)

/**

• sed_term * **/

sed_term --> global ^ recognize >> action | recognize >> action | unix_sed_term

global --> word_term

action --> expression

unix_sed_term --> a_rule | al_rule | b_rule | bl_rule | w_rule | wl_rule | s_rule | sl_rule | d_rule | dl_rule

This forms a subset of the unix sed command, and 'l' means 'longest match first'.

/**

• kind * **/

Section 4. Kinds: Conditional Equations

In this section, bracket notation [...] means that it is optional. Spaces in the syntax are meaningless and are used only as syntactical delimiters.

General form of definition of a kind.

:- bekind(kind_name [, Options] ).
kind_rule_1
kind_rule_2
  .
  .
  .
kind_rule_n
:- ekind.

kind_name --> [module_name:] atom [//N]

where N is a non-negative integer.

A kind_rule is any of the following forms 1, 2, 3, 4:

(1) term = exp [ :- goal] (2) with(args, term) = exp [ :- goal] (3) term = with(args, exp) [ :- goal] (4) head [ :- goal]

Currently, only flip option is supported:

flip([j1, j2, .., jn])

where a series j1, j2, .., jn is a permutation of 1, 2, ..., n.

The flipped version g of f works as follows:

g(aj1, aj2, ..., ajn) <==> f(a1, a2,..., an).

Sample use of xflip and flip in KIND.

:- bekind(residue, []).
X - Y  =  xargs([A, U, V] :- append(U, V, A)) @ X @ Y.
X = `X.
:- ekind.

% ?- misc:residue(([a,b,c,d,e]-[a,b]-[c]), R).
%@ R = [d, e] .

:- bekind(flipped_residue, [flip([2,1])]).
X - Y  =  xargs([A, U, V]:- append(U, V, A)) @ X @Y.
X = `X.
:- ekind.
% ?- misc:flipped_residue(X, ([a,b,c,d,e]-[a,b]-[c])).
%@ X = [d, e] .

:- bekind(ff//1, []).
a =  `f(a).
b =  `g(b).
X =  with(A, `C) :- memberchk(X-H, A),
        C =..[H, X].
:- ekind.

% ?- misc:ff([c-h,d-k], c, V).
%@ V = h(c).

% ?- listing(misc:ff).
%@ ff(_, a, f(a)).
%@ ff(_, b, g(b)).
%@ ff(B, A, C) :-
%@ 	memberchk(A-D, B),
%@ 	C=..[D, A].
%@
%@ true.

1. Glossary 5.1 Meta variables in the BNF.

   meta variables meaning -------------- ---------

   atom atomic_term basic_callable_term basic_exp basic expression callable_term canonical_exp canonical expression character character_class code comma_list_of_meta_arg escape_symbol exp expression extra_condition extra condition function_rule global term for indicating globals. goal body of a pac rule. head list of parameters i_character_class character class as integer intervals i_interval an interval of integers i_interval_list list of intervals i_point an integer integer an integer integer_interval interval of integers interval interval of integers interval_list list of intervals of integers kind_name name of a kind kind_rule rule of a kind list list in Prolog macro_name atom markup_rule rule for the markup language meta_arg meta argument module_name module name pac_function nameless function pac_pred nameless predicate pac_rule rule of nameless predicates pac_rule_head parameter list of a pac rule pac_term term for a nameless predicate phrase phrase extended with words positive_integer positive integer including zero prolog_atom prolog_list prolog_module_name prolog_number prolog_string prolog_term regex regular expression string regex_string unix-like regular expression sed_term sed expression string term variable word hybrid regular expression word_term hybrid regular expression

   5.2 Reserved keywords/functors for PAC

   functor/arity meaning ------------- ----------- bekind /1,2 begin of a kind group. char /1 charater class as intervals ekind /0 end of a kind group flip /1,2 permutation for flipping arguments fun /1,2 function definition if /2,3 'if' statement inf /0 symbol for the imaginary least integer mrec /1 system of equations for recursive predicates out /1 the complement of intervals of integers. pipe /1,2 DCG-like definition with globals. pred /1,2 nameless predicate psf /1 sentential form a la phrase grammar quote /1 quoted expression rec /2,3 recursive nameless predicate definition rev /1 reverse operation of automaton sed /1 sequential editing command in phrases sup /0 symbol for the imaginary largest integer w /1,2,3 regular expressions of shortest match mode with /2 expression in a kind rule with hidden aruguments wl /1,2,3 regular expressions of longest match mode xpred /1 macro for flipping arguments.

   5.3 Symbols

   functor/arity annotation ------------- ----------

   @ /1 call a named regular expression @ /1 expand expression twice @ /2 application (as term completion) @@ /1 automatic searching arguments for expanding ->> /2 a markup language rule :- /2 pac rule & /2 grouping pac rules & /2 intersection of two words -> /2 mapping rule of a function \ /2 mapping rule of a function :: /0 context kind :: /2 expression with a kind ` /1 quote # /1 term completion operator : /1 last-argument-for-return-value mode [] empty string in a word . /0 match any charactor + /2 concatenation on words | /2 UNION / OR of words \+ /1 Negation of words ? /1 apply at_most_one time \ /1 escape symbol ^ /2 word with repeat control ! /1 negation operator in regex.