NAT'L INST. OF STAND & TECH R.I.C.

AlllDS

. NBS

Publications

NBSIR 80-2182

M7: A General Pattern Matching

Facility Users Manual

A. R. Marriott

G. H. Skillman

S. B. Salazar

W. T. Hardgrave

Application System Division

Center for Programming Science and Technology

Institute for Computer Sciences and Technology

U.S. Department of Commerce

National Bureau of Standards

Washington, DC 20234

January 1981

C- DEPARTMENT OF COMMERCE

100 iTIONAL BUREAU OF STANDARDS

.056

80-2182

1981

NBSIR 80-2182

M7: A GENERAL PATTERN MATCHING

FACILITY USERS MANUAL

ATlOJfAL BCBBAU

or aTAMDABUB

LUBABT

MAY 2 2 1981

IQ o

/

'

A. R. Marriott

G. H. Skillman

S. B. Salazar

W. T. Hardgrave

Application System Division

Center for Programming Science and Technology

Institute for Computer Sciences and Technology

U.S. Department of Commerce

National Bureau of Standards

Washington, DC 20234

January 1981

U.S. DEPARTMENT OF COMMERCE, Philip M. Klutznick, Secretary

Jordan J. Baruch, Assistant Secretary for Productivity. Technoiogy, and Innovation

NATIONAL BUREAU OF STANDARDS, Ernest Ambler, Director
'_**yAU* jA9UirrA»

I ntAittt

S S

..l-v.w ;^: JAW3VI30 A :tM

mm JAUVI^ 8R38U YTUIOA’I

fe'.* : ’"

•

'

. » ,

; Y,„ i: ; '5?

' ’ygoioarfe^t bo« t»3(rt«*o8

"" ;.^

r'"»3iamiT«0''te> .:-'-
A General

M7:

Pattern Matching Facility

Users Manual

A. R. Marriott

G. H. Skillman

S. 6. Salazar

W. T. Hardgrave

November 1980

Version 3-0

Application Systems Division

Center for Programming Science and Technology

Institute for Computer Sciences and Technology

National Bureau of Standards

Washington, D,C.

M7 is a pattern matching and replacement facility developed as a UNIX tool for translating

and reformatting queries, languages, and data. M7

operates by first preprocessing a set of user defined macros, then using these macros to match and

replace the text in an input string. The enabling

of the rescan option directs M7 to match and

rematch the macro patterns against the input

string until all possible replacements have been

made. Three construct ions--tags , stacks, and

count ers--allow communication between different

macros and different input strings, to permit such

functions as line numbering, labeling, and argument passing. This paper includes a tutorial

which shows how to construct a set of macros to

solve a typical problem using, as an example, a piece of a FORTRAN to C translator.
*4j

J tN ' ^

t^illtttt tftS43i'^*H XH4«9»0 A

Ri ^ -

' TM<- ^ --i-* -^.

" %a »<^''"^i-'‘

.ir ^’ XHMUft. ., . J»S«])G».

^T*' ,. ?l:

na«XiX3l8^^^H,, :©'. ,, jrl'pi

‘

! ’*2 |»y»4§ik'T4t

.^r—

W *. cr-W^

' <-0»£, aot«'^«f

' ^ .;'.V ; .;*:« ly m..

-.. . . i-rTMiJb-.^' i 1

fra* menii^7 0'& '*•1443^

X«oi4atfOft^btf* aafr««X'i« 4*i'tt«ifo.O 0;tpJJi:i a nl ^

_

'.id^- ' ' " efrt'afra* 4£ !»!* 4*14 ai &TMmi ^ '

fL

Wli‘

’

-. ’'4 > .y

, V^< V —-v>^"

'?».

. '^T’ "its

tH’ "^4j8fr :fr<t,» ji4i4'4*mdiai''fraaii^^f

'44i«ft' A 4o4-^%t4s «a4«n»<t4 " 'j t>n,8 4aJ'&a fff{f^-%mo^&4k^t>0 it:il; ' . 3^0-lX tf'T'^'-: ^'141

' 'rt'ji' -ai'iiA x» 4gfr tl 4

i)fl«' fr ft4'0«'i'',I^Tfr^i.;fl 01444^' '0*oeaf®'»44 lo

ioQi»x"^$4:4''''"^-'44^1A^^ on.AiMI ,i!fr'44 4fr4»^'»t '^lii nit^aej ». Vn,rf ’iti ' ©-414A'f'

^*('4'

: '''''fr-i;*^! A» 44 ' X

i

' i

4 na• 8«:'i t,4 fr frn«’ ;j^Ji3(^«i;«. , «>frAr'

J na‘1^5'1 X <1 :©, X^t%ci4,o,^ ' woXXa-*’i^

do*» r’’4 Xia4a4 ' ’s>Jpr.:a'j^'^© o,a^'l", 4is:i^^llfr': ,frfl*:»ao"s©*•

•u$'ta;4fr(5« «dpl4fraat

laiToxa'a . a

.

M , © X««,fl T® "'n«.' 6,«* , , ao»i 4 - o «,

'

•• V

':^»' ' .J: (- ^' ' -9
FEDERAL INFORMATION PROCESSING STANDARD SOFTWARE SUMMARY

01. Summary date

Yr. Mo. Day

fL n 2 n. 2.

04. Software date

Yr. Mo. Day

.a. SLXLS. 1.X

02. Summary prepared by (Name and Phone)

Sandra B. Salazar X3491

05. Software title

M7: A String Pattern Matching Facility

06. Short title ML

03. Summary action New Replacement Deletion B

Previous Internal Software ID

07. Internal Software ID

08. Software type

Automated Data

[~~) System

Computer Program

|~| Subroutine/Module

09. Processing mode

[~] Interactive Batch

[~^ Combination

10. GeneralApplication area

Computer Systems

Support/Utility

[~| Scientific/Engineering

Bibliographic/Textual

Management/

[~| Business

Process Control Q Other

Specific

Pattern Matcher

11. Submitting organization and address Application Systems Division,

National Bureau of Standards

Department of Commerce

Washington, DC 20234

642

12. Technical contact(s) and phone

S. B. Salazar

W. T. Hardgrave

921-3491

13. NarrativeM7 is a pattern matching and replacement facility developed as a UNIX

tool for translating and reformatting queries, languages, and data. M7

operates by first preprocessing a set of user defined macros, then using

these macros to match and replace the text in an input string. The

enabling of the rescan option directs M7 to match and rematch the macro

patterns against the input string until all possible replacements have

been made. Three constructions -- tagSi stacks, and counters -- allow

communication between different macros and different input strings, to

permit such functions as line numbering, labeling, and argument passing.

14. Keywords

macroprocessor; pattern matching; query processor; software tool

;

text processor; translation; UNIX.

15. Computer manuf'r and model PDP-1116. Computer operating system

UNIX

17. Programing language(s)

c

18. Number of source program state- ments _3K

19. Computer memory requirements 20. Tape drives 21. Disk/Drum units 22. Terminals 64K NA 1 1

23. Other operational requirements

I 24. Software availability

Available Limited

26. FOR SUBMITTING ORGANIZATION USE

25. Documentation availability

In-house only Available Inadequate

0

In-house only

185-101 Standard Form 185

1974 July

U.S. Dept, of Commerce—NBS

(FIPS. Pub. 30)
99^-^SS - O H6I : OdO

'uo!)ej3do |BUia)Uj jo^ |ti^n paiuaap

uoi^eujjopjj Aue uie^uoa Aeiu )| 'Ajeiuujns S|M) 8u|U!Uiqns uoi^ezmeaio aq) >o asn aq) Mt papjAOJd s| eaje s|qi *8sn uonaziuaSiO Su|U|Uiqns Joj '9^

*a)ep A^jiiqeijeAe papadxa aq) Moqs ‘„a)enbapeu|„ Xijuasaxl Sj uojte^uauinaop ‘aiqjssod ‘aiqeijeAe Sj uoqetuauinaop aq) qaiqM u| uiJO| pue aajjd aq^ se naM se ‘)u|od ;at)uo9 auoqd jo ||eui a apn|ou| '„aiqe|jaAv„ si uoi)e)uauin3op *X|uo asn asnoq-u| joj pua ‘uonnqiJ|sia Jo^ atanbapa

•u| “oiiqiid aq) O) aiqaiiaAV :8uouia umj^ ^jnqaiiBAa uo|)a)uaiunoop aq; saqjjosap )saq qaiqM xoq a^ajjdojdda aq) qjayy 'X)|||qa||BAV uonatuauinooQ *sz

'aiqissod ‘aiqaneAa S| ajaMi^os aq) qafqM u| ujjo| pue

33ud aq; se naM sa ‘)UjOd pa)uo3 auoqd jo |jauj a apnpu) ‘..aiqaijeAv,, S| ajeM^os aq) || 'Aiuo asn asnoq*u|-Joj pue ‘(A|uo asn )uaujujaAo8 jo| :'8*a) X;i|!qe|jeAv pa)iuin ‘aiiqnd aq) oi siqa||aAV :8uouie ujoj| AtniqeiiaAe ajeM^os aq; saqpasap paq qoiqM xoq apiJdojdde aq; )peM ’XmiqeiieAV ajBM)^ ’pz

'Sjauo|d 0!qdej8 ‘uimoJO|ui )nd;no-ja)ndujo3 'aijuijsae^ ‘saajAap japejeqa |eoj)do “8'a 'aAoqa papoipuj ;ou tuauid|nba papiaj jo ‘ajeM^os poddns ‘saaiAap lejaqduad Aiquapi *s)uaujaj|nba)j lauonejadQ jaqio CZ

-op ‘az|s au||/uaajos *ps japejeqo ‘paads ‘adA) ‘leojtijo /i ‘^joads ‘pajjnbaj S|eu|uua) jo jaqujnu A^i^api ’S|au|uijai ‘zz

• 0i» ‘lapoiu ‘jajnpe^nueiu ‘lesquo >| ‘^pads 'ajeMUOS a^ado o) papaau (6l UJ8)|—..Ajoiuayv,, se s}jun aujes u|) azis pue jaquinu Aji^uapi t)|un uinja/qsia 'iz

‘o;a 'A)|suap 8ujpjoaaj 'sqosj} 'ppoui ‘jajnpainueuj ‘paquo ‘^toads 'ajemuos apjado o; papaau jaqujnu ^j;uap| 'saAiJQ adei *oz

'(CI u<a)!) aAjpjjeN aq) uj s)uaiuaj|nbaj Aioujauj lenvijA Aiipapi 'tfun jad s)iq p jaqiunu pue *-op ‘sjapejeqo ‘sa^q ‘spjOM A^jaads 'uiapAs

8u;;ejado aq) jo^ pajmbaj Ajouiaui p aApnpxa ‘ajeM^os a^naaxa o) Aiessaaau Ajoujauj pujapj luniujujiu Jap3 *s)uauiaj)nba)| Ajouiay^ ja^iduioo *61

-ap ‘sauqnojqns pauea ‘sojaeiu apjedas ‘ajeM^^os Sjqt ui spaiuapp apnpu| -stuauiate^ uiej8oJd aajnos to jaquinN '81

•ii Hinais

‘911 IdldOSV^IS ‘A NVdlHOd ‘10803 ISNV “8‘a iuojSJOA 8ujpnpui ‘uaujjM s| ajeM^os aq; qaiqM uj (s)a8an8ue| aq) A^jpapi -(s)a8en8uai SujUjej8oi(| *^i

'(El uia)!) aAitejjeN aq^ ui spauiaauequa A|j;uap| ‘8uqejado sj ajeM^os qajqM japun aseapj pue 'jaqiunu 'auieu japa -uiatsAs 8u.qejado J8)nduio3 ‘ 9T

‘leuojpjado st ajeNq^os qajqM uo (s)jatndujoa auiej^ujeuj A^quapi ‘lapow pue jajnpepiueM japduioo 'sx

'suopajoias q;|M sajjpa apjedas 'ajeM^^os aq) p sajnpa^ pue suo|xeai|dde ‘suo|pun| aqx paqaj qajqM sasejqd jo spjoM xueaj^ju8js pj-j 'spjoMAa)| '^x

'axejjdojdde ^j ‘saauajapj ajjQ sajnpa^ ajoMpjeq anbjun pue ‘sxuauiajjnbaj Ajouiauj fenvijA ‘ejpauj jndxno pue xnduj 'ajeM^^os jaqp o; sdjqsuojpjaj ‘sujaauoa Aijjnaas ‘suoj^ea -qipouj luapAs Sujpjado jejoads se qans sjope/ )ueauju8js apnjaui ‘uojxnjos p spoqpui pue passajppe luajqojd aqi Ajasjauoa aqjjassQ *aAjiejjeN 'EX

‘XX ujaxj uj pqx ujoj^ xuaja^jp |j ‘ssajppe 8uj|jeiu pue ameu uojpzjue8jo apjAOJj ‘apoa eaje auoqdaja; apnjauj -ajeM)^os p

spadse leuojpjado jo/pue jaueui pafqns uo uojxeuuopi pajuqaax jo^ papepoa aq o) (s)aajj^o jo (s)uosjad japa :auoqd pue (s)pepoo jeajuqaax ‘ZI

‘apoa dIZ pue 'app ‘Axja ‘ssajppe pajp ‘apoa ijeui Sujpnpuj ‘ssajppe 8uj|jeuj apjduioa uj iijj ‘jjaunoo jo ‘uojssjuiuioo ‘uojpjodjOQ ‘aajAjas ‘(uojpjpjujujpy/neajng) paujviedea ‘Aaua8v 8ujpn|auj )nq

‘laAaj uojSjAjQ JO qauejg aq; O) ‘aiqjssod se Ajspidujoa se sjeM^os aqx jo; sjqjsuodsaj uojpzjueSjo aq; A;j;uapi ‘ssajppy pue uo|;ezjueSJO 8ujpjiuqns ‘XX

„‘j8qK}„ Sj eaje jejauaS aq; ;j ajaq a;ejoqeia ‘3;a :„ss8Ujsng/;uauja8eueM„ sj eaje lejauaS eq; t\ ..llojAed,, :„A;!|j;n/vioddns suja;sAs ja;nduj03„ sj eaje |ejaua8 aq; ;j „jazjUJj;do 10803m "S'e :uoj;eaj|dde ;o eaje-qns aq; A;j38ds :a|;j38ds

jaqx) 8ujjaau|8ua/3|;i;ua|3S

|enpax/3|qdej8o||qjg ssaujsng/pauj88eueiq

pjpoQ ssaaojd Apiui/Vioddns suiai^s Japduioo

:8uouie poj; uO|;eaj|dde ;o eaje |ejaua8 aq; saqjjasap ;saq qajqM xoq o;ejjdojdde aq; MJe^ qejauac)

‘eajy uojxeajjddy *ox

-8jeM;;os aq; saqjjasap ;saq jaAaqaiqM ‘apouj uogeuiquioo jo *qa;e8 *aA|pej8}U| ue jo; xoq a;ejjdojdde aq; qje^ ‘apopi 8ujss8aoJd ‘60

‘ajBMUos aq; saqjjasap ;saq jaAaqajqM

‘a|npoM/auj;nojqns JO ‘ujej8oJd japdujoQ ‘(sujej8ojd ja;nduioa ;o ;as) uiapAs e;ea pa;euiopy ue jo; xoq a;ejjdojdde aq; >|jeM ‘adAi ajeM;ps ‘80

‘apoa JO jaquinu uoj;eaj;j;u8pj anbjun e J8;ug 'ai ueMxps leujapi *xo

‘ajeMUOS aq; S8j;j;uapj qajqM pAuoJae jo uoj;ejAajqqe pasn ApoujUiOa ja;ug (|euoj;do) ‘8|;ji p>qs ‘90

-aiqjssod se aAjyljjasap se ai;j; atje^ *a|;ji. ajeMUOs ‘SO ‘OOMNAA :;eujJo; Aea ‘qpoM 'Jeax asn ‘pa;epdn ;se| jo po;a|duJ03 seM ojeMuos a;ep J8;ug -apo ajeMyos ‘tO

•ujjo; sjq; uo xx Pue eo ‘20 ‘TO

siua;i A|uo a;a|dujoa :Ajeiuujns |eu!8jJ 0 aq; p /o uja;j uj paviodaj se uoj;eayj;u8pj ajeMuos |euja;uj aq; „ai ajeMuos |euja;u| snojAaJd,, japun ja;ua

‘pa;8|ap aq o; sj Ajeujujns ajeM^os e ;i Ajeuauns Mau e jo; se suj8;j jaq;o qe 8;a|diuoa :uuo; sjq; ;o /o uja;j uj uoj;eaj;j;uapj ajeM^os jeuja;uj Mau

aq; ja;u 3 pue ‘Ajeuiujns jeujSjJO aq; ;o iQ uia;j uj pauodaj se uoj;eay!;uapj ajeMuos |euja;uj aq; ,.qi ajeM^og |euja;u| snojAaJd,, Japun ja;ua ‘;uaui aaejdaj e si Ajeujujns ajej^ps sjq; ;| Ajeuiiuns p uojpiap jo Ajeiumns ;ueuioaepaj ‘Ajeumins Mau jo; xoq a;ejjdojdde aq; qje^ ‘uojpy Aieuiuins ‘EO

‘Aieujujns sjq; pajedajd oqM lenpjAjpuj p (apoa eaje 8ujpn|auj) jaqiunu auoqd pue aiueu Ja;u3 ‘Ag pojedajd Ajeuiuins ‘ZO ‘aONNAA :;eujJo; Aea ‘q;uo^ ‘jeax asn ‘pajedajd Ajeujiuns a;ep J8;ug ‘a;ea Ajeuiuing ‘XO

SNOIlOnHlSNI
TABLE OF CONTENTS

Page

1. INTRODUCTION 1

1 . 1 BACKGROUND 1

1.2

DOCUMENT OVERVIEW 1

2. MACRO FILE 3

2.1 MACRO DEFINITION 3

2.2 FILE FORMAT 3

3. PATTERNS ; . . 5

3.1 GENERAL PATTERN MATCHING 5

3.2 SPECIAL CHARACTERS 5

3.3 TAGS, STACKS AND COUNTERS 11

4. REPLACEMENT DEFINITION 13

5. STACKS 15

6. COUNTERS 17

7. RESCAN FEATURE 19

8. CONTROL COMMANDS 21

9. EXECUTION OPTIONS 23

10. USING M7 25

11. FATAL ERROR MESSAGES 29

12. CONSTRAINTS AND LIMITATIONS 31
y ''if/UU'

mg^'/

|^vi-«- 0$^

, »'^jiNi*.''#'ii «wi '%gin

• » * <' •' *%,- - -IT • t' ,"•! • :<• '*' * ‘nj’ 4'. '4^

' *** It# ml ;|[;^ #g4.>ii l iwtpiii* -<1

fT^4 •*•€ f ^ *1 1 V A.W«HaI«^V\4 f >• .'i

"t .>•*•« • • • • *' «

,

* «;»‘J-fi •.'*'< • • •.'«>|i!''»

•

» « 4'* •:,

^ vllJAH i » ^• . >

»' f W ^tm0, Jr

"aa f' J T» , :SA!it„:. **

' "" *"'"*

'f

* ” * '

-^5, ^**|i»r5fW 5^, ,.; S

.

, M

'' 'v!^'' It . Sit ''•j-.f'’' - ' '^i. *.rt'«*l A

n."'* U'P«4 •«"

‘f\ . •flj er

v'.'- %.« >.'«*% • •.*• •• J'i-v. 2aiiAMM<iWa®Bwfi«;

£i ,. . ^.,y. . •

.

. * .•'i.i 'V'V^V

' ,' '> •• ' -

'

' li^ iM « » 4#»#^

i'f £ i .r * *^ • f'* • • «

*' ' iP'»'W'7^*Si^V^^WT WUX l v3 2ny^|jJL '#>)l>*'gdM —^

,

,

•'

'

. "

„.. ^ _ A,'

^-•' '^'Ak.V '.. «

’

' ^-r^^lb'' T«.«H ®Mt y»'js#';f^

--» v’iiiaww «;’

«•<!'«" ‘1 ',^1 '^M‘‘-^^' *^*'

lW*v *'«

»V-

'»: 'TtiV""-

' '

M.’’ '' ,iH

rK: "I

+»r I o*j
1. INTRODUCTION

M7 is a general pattern matching filter designed and

implemented at the National Bureau of Standards (NBS). It

is a useful tool for translating or reformatting queries,

languages, and data. M7 is particularly useful and costeffective for one-time' translations from one format to

another or in a research environment to demonstrate the

feasibility of a transformation.

M7 repetitively matches and replaces the text on an input string under the control of a set of user defined macros. The process consists of two stages: (a) preprocessing

the macro file, and (b) matching and replacing the input

string. In the first phase, macros are read from the user’s

file, preprocessed, and stored on a second file. In stage

two, the patterns are compared, in a line-by-line manner,

against input strings read from standard input. Matching

and replacing continues until all of the patterns fail to

match the input. The final version of the altered input

string is sent to standard output. Figure 1.1 shows the M7

information flow.

Complete examples of the use of M7-”-macros , input strings,

output text--are available on-line from the authors.

1 . 1 BACKGROUND

M7 is written entirely in the programming language C

and consists of more than 40 modular subroutines and functions. Several routines are C versions of programs contained in Software Tools [KERN76] which have been modified

to support the more powerful features of M7 . M7 is an extension of M6 [HALL71] and MORTRAN [COOK733 and has also

been influenced by ML/1 [ BR0W7 4 , COLE? 6 ] and STAGE2 [WAIT70].

For more information about the internals of M? see the MX

Software Internals Manual [SKIL80].

1.2 DOCUMENT OVERVIEW

This doc

using M?

and 4 discuss

emphasiz ing

cial meanings

matching and

6 deals with

ument presents t he in forma t ion ne ce ss ary for

Sect io n 2 desc r i be s the mac ro f ileSe ct ion s 3

the p attern a nd th e repl acem ent d ef init i on

,

the ch aract ers a nd c on s true t ion s th at h ave s pe-

. The use of St ac ks t o save text fo r la ter

r eplac ement is d es cr ib ed in sec t ion 5 • Sect ion

count

rs which c an b e used for tas ks such as

1 -
line numbering. Section 7 discusses how M7 uses the macro

file to repetitively match the text on an Input string.

Section 6 describes how to generate new macros from other

macros and section 9 lists the calling options for M7 . A detailed example which shows how to create and arrange macros

to solve a specific problem Is provided In section 10. Error

messages and constraints are the topics of the closing sections .

I I

I PREPROCESSED I

I MACRO I

I FILE I

I I

I

I

I I

I V

1

1 USER’S!

MACRO ! > FILE !

1

1

1{MACRO

{FILE

IPRE-

{PROCESSOR

1

1

1

1{PATTERN

{MATCHING

{ AND

{REPLACING

{HANDLER

ALTERED

_ _ _ „ s STANDARD

INPUT OUTPUT

STRINGS

I

1

1

1

1 M7

USER’S

INPUT

STRINGS

STANDARD

INPUT

Figure 1.1 - M7 Information Flow
2. MACRO FILE

M7 is called from the UNIX shell level in the following

manner:

M7 <options> <macro file>

The macro file contains the pattern matching and replacement

Information which M7 evaluates when processing input text.

It consists of macro definitions which have two main parts:

a pattern which is matched against an input string, and a replacement definition which is substituted for the matched

substring. The options specify execution alternatives.

This section will explain how to set up the macro file.

2. 1 MACRO DEFINITION

The macro file consists of macro

basic form of a macro definition is:

definitions

The

* <pattern> ' <replacement

symbol>

* <replacement

def inition>

<stack/counter

commands>

The symbols surrounded by angle brackets (<>) are metasymbols; however, single quotation marks must surround both

the pattern and the replacement

ition must terminate with a symbol can be either tt _ ti or

definition. The macro definsemi-colon. The replacement

as discussed in section 7.

Stack and counter commands are usually placed after the

replacement definition. These constructions are identified

by a leading or "A".

2.2 FILE FORMAT

The use of delimiting characters for the pattern, replacement definition, and the entire macro definition provides flexibility in formatting the macro file. The user

may insert spaces and comments freely to make the file more

readable

- 3 -
Arbitrary spacing Is allowed. For example:

*A* = *A*=’B*

•A*= ’B»;

all function Identically.

All characters outside of the pattern and the replacement definition, other than the replacement symbol and the

stack and counter commands, are Ignored. Thus, no special

delimiter Is needed for most comments. An example of a commented macro file Is:

'girl'; this macro changes boy to girl

'

' ; this macro shrinks spacing

'

' ; this macro deletes the character a

'boy' =

' ' r «a' =

( end)

'B'

Any text surrounded by slashes Is Ignored. This

feature allows comments to be Inserted within a pattern or

replacement definition. It also permits arbitrary splitting

of a macro definition across line boundaries. For example:

'FIND THIS TEXT' = 'AND REPLACE IT /

/ WITH THIS TEXT'

A macro definition may also be continued by placing the

pattern and Its replacement definition on separate lines.

An example of this is:

'Replace this very long line' = 'with this very long line';

More than one macro definition can be placed on a line.

For example:

'A'='B'

'C ' r *D ' ; can be written as:

'A'r'B' ; 'C'='D'

( end )

- 4 -
3. PATTERNS

The pdti:ern matching facility ia the heart of M7 • Sections 3*2 and 3>3 will discuss the important features: the

special control characters, tags, stacks, and counters. The

algorithm for matching a pattern with an input string will

be presented in section 3.t.

3.1 GENERAL PATTERN MATCHING

The algorithm for pattern matching is as follows:

1 . Get the first character of the input string

and set N : s 1

.

2. Get the first character of the pattern.

3. Do the current pair of characters match?

If not, go to step 5.

M. Get next pair of characters.

If end of pattern, return MATCH.

Otherwise, go to step. 3*

5. Backup to beginning of input string + N.

If N = lengthCinput string), return FAIL.

Otherwise, set N := N+1;

get Nth character of input string

go to step 2.

3.2 SPECIAL CHARACTERS

Table 3.1 lists the characters which have special meaning in patterns. These characters and their associated concepts will be described below.

Delimiting characters

A matches the null character at the end of a line.

For example, the pattern:

The back$

will match:

The back

but not:

(end)

The back end
A

'** matches the null character at the beginning of a

line. For example, the pattern:

'‘front part

will match:

front part

but not:

the front part

(end)

.

- 6 -
CHARACTER

1

1 FUNCTION OF THE CHARACTER

1

$

1

1

i Matches the null character at the end

1 of the line.

I A

1

1 Matches the null character at the beginning

1 of the line.

i Matches one or more characters of the

1 preceding type of character. (Closure 1)

1

1 Matches zero or more characters of the

1 preceding type of character. (Closure 2)

! []

1

! Matches any of the characters listed in

1 the brackets. (Character class)

1 -

1

! Indicates a range of characters in a

! character class.

1

! Matches anything not listed in a

1 character class. (Complement)

' ?n ! Matches a character that is in special

! character class n. 1 <= n <= 6

& 1 Refers to an entry on one of 26 stacks.

1

1

! Refers to a counter or its increment.

•{} ^

1 Tags or refers to a portion of input text.

1 /

1

! Skips to the next slash. (Line continuation)

1

\ 1 Escapes any of the special characters.

1

Table 3-1 - TABLE OF SPECIAL CHARACTERS
Character class

The construction " [ c1 c2c3 • • • cn] " , termed a character

class . tells M7 to match one of the characters specified

between the brackets (i.e. cl, or, c2, or, ... cn). For example, the pattern:

[abcdef

]

will match one of the first six letters of the alphabet.

A range of letters or digits can be specified using a

dash. For example, the pattern:

[a-c]

will match 'a', *b', or 'c*. Also, the pattern:

[0-3]

will match *0’, *1*, *2», or *3*.

The use of ' "as the first character in the character

class reverses the meaning of the construction, so that a

match will occur only if the input character is not found

between the brackets (complement). For example, the pattern:

[“a-z]

would match any character that is not a lower case letter.

Several frequently used character classes can be abbreviated by using the construction "?n", where n is a digit

between one and six. These are:

?1

?2

?3

?M

?5

?6

matches any

matches any

matches any

matches any

matches any

matches any

character

.

alpha-numeri

alphabetic c upper case 1

lower case 1

digit

.

c character,

haracter

.

etter

.

etter

Escape character

A backslash *\' escapes the special meaning of the

character which follows it. For example, the pattern:

\«

matches the character The escape character can be escaped by typing "\\". Two alphabetic characters have

- 8 -
special meaning when they are escaped. "\n" matches a line

feed and "\t" matches a tab.

The following characters lose their special meanings

under these conditions:

Character Cgadit.lOD

- At the end of a character class construction

or outside of a character class construction.

* Not at the beginning of a character class

construction or outside of a character class

construction.

? Not followed by a digit between 1 and 6.

Any special character Within a character class,

other than or

Closure

Closure is an important concept in M7 . The closure

character matches one or more additional characters that

meet the same specifications required of the preceding character. For instance, the pattern;

[ab]

will match a character if it is an ”a” or "b". Thus, the

pattern:

[ab]*

will match a string of "a”’s and "b”*s. Also, the pattern:

a*

will match a string of "a”'s, the pattern:

[~a-zA-Z]*

will match a string of non-alphabet ic characters and the

pattern

71*

will match any text.

The closure character repeats the previous pattern construction and therefore a pattern cannot begin with "*",

"{*}", or since there is no previous pattern with

which to check succeeding characters in the input. The closure construction may only follow stack and counter calls

that refer to the input string (namely, type 1 - refer to

-9
chapters 5 and 6). The construction *>•«" is meaningless

since the second closure has no pattern preceding It.

Cloatir.c alRQ-cLUm

M7*s closure feature uses the following algorithm:

1. Match the longest string possible.

2. Does the rest of the pattern match?

If yes, Indicate success and terminate.

3> Did the previous character match this closure?

If yes, back up one character and

go to step 2.

4. Was there a previous closure?

If yes, back up one character from the

last character matched In the previous

closure and go to step 2.

5. Indicate failure and stop.

An Illustration of multiple closure patterns, which are handled by the fourth step In the algorithm. Is the pattern:

?1»[0-9]»

with the Input text:

Mozart's 38th symphony

M7 will decrease the number of characters matched by the

first closure until the second closure Is able to match the

'8' upon which the pattern succeeds.

Z?X9 closure

The zero closure matches zero or more characters

that meet the same specifications required of the preceding

character. It can be used In the same manner as the regular

closure.

Example

Here are a few additional sample patterns and some of

the Input texts that would match:
t

PATTERN TEXT

would match

or

TAB

JB

'‘[1-3][ABC]?3$ would match 1BE

or 3AT

??3« would match

but not

Tslngleword

??333

3.3 TAGS, STACKS AND COUNTERS

Tags, stacks and counters are three features that distinguish M7 from other pattern matching and replacement programs. These structures allow communication between:

The usage and form of a tag, stack, or counter construction

depends on whether it appears on the pattern or the replacement side of the macro definition. Basically, on the pattern side, the current value of a tag, stack, or counter is

matched against the input string, whereas on the replacement

side, the current value of the tag, stack, or counter is

used to alter the input string. The applicability of these

constructions to the pattern will be discussed in this section, while their relevance to the replacement definition

will be presented in section Sections 5 and 6 will discuss stacks and counters in detail.

The construction ” { <pat tern> } " tells M7 to remember the

text which matches the pattern between the braces for use in

later processing. The occurrences of these "tags" in a pattern are numbered; the first is numbered 1 and so forth with

up to 99 tags per macro. For example, if the pattern is:

then M7 will remember "ea". Tagged text can be used in the

a. the pattern and replacement definitions

of a macro,

b. independent macros, and

c. different input strings.

Tags

h{ [aeiou] • }d

and the input text is:

head

11-
replacement definition or stored on a stack. 1

Tags can be nested in the pattern. For instance, the I pattern: I {ab{cd)e{ f {ghi} } } {J)

|

will remember "abcdefghi" as tag #1, *cd” as tag #2, "fghi” { as tag #3t "ghi" as tag #4, and "J” as tag #5. That is, the

left brace determines the ordering. |

I Stacks '

The construction "&(i)", where "i" is any lower case

letter, causes M7 to match what is currently being refer- j enced in the stack identified by "i”. For example, if stack l "a” contained the text "tony" then the pattern: | He is &(a) I

i would match: j

I He is tony

I and the pattern:

I the world needs more &(a)*s !

I would match: i

I

I the world needs more tonytony tony tony s | (end).

i

^

li Counters * |i The construction "#(i)", where "i" is any lower case

letter, matches the current value of the counter Identified i by "i". For example, if counter "b" were "20" then the pattern:

j go to #(b)*

would match:

go to 2020

( end )

.

- 12 -
M. REPLACEMENT DEFINITION

Nhen a portion of the input string matches a pattern,

It Is replaced by text as specified by the replacement definition. The replacement definition can consist of any sequence of characters. As In pattern matching, certain characters have special meaning.

T.a«g

The construction "{n}** is replaced by the text matched

by tag number n where n is from 1 to 99> This tag number

refers to an occurrence of a tag In the corresponding pattern (see section 3>3)> The first tag would be tag number

1, the second tag would be tag number 2 and so forth. The

construction Is useful for such tasks as passing arguments

from the matched text. For example, suppose there Is a' pattern :

ADD, {[A-Z]») ,{[0-9]»} ,{[0-9]«}

with replacement definition:

n} = {2} + {3)

Then, the input string:

ADD, A, 24, 100:

would be replaced by:

A=24+100

( end )

.

Stacks

The construction "&(!)" is replaced by the text

currently referenced in stack "i". For example if stack "a"

contained "car", then the replacement definition:

my & ( a

)

would cause M7 to replace some matched string with:

my car

A detailed discussion of stacks can be found in section 5.

- 13 -
Counters

The construction "#(1)" is replaced by the current

value of the counter "i". For example, if counter "b** were

100 then the replacement definition:

go to #(b)

would cause M7 to replace some matched string with:

go to 100

Refer to section 6 for a detailed discussion of counter oon*

structions.

- 14 -
5. STACKS

M7 supports 26 user stacks. Each stack Is Identified by

a lower case letter, called the stack Identifier . and has

its own stack pointer . In the current version, a stack has

at most twenty entries, each of which may have fifty characters. The purpose of the stacks Is to save text for later

use In the matching and replacement parts of other macro definitions. The stacks may also be used as simple variables.

constructions

There are four basic stack call constructions. All of

these may appear in the replacement definition. Types 2, 3i

and 4 may be used in the stack command. Only type 1 may appear in the pattern. The stack call constructions are:

1. "&(!)" is replaced by what is currently being pointed to in the stack identified by *1*.

2. "&(n,i)" puts the text matched by tag number n onto

stack 'i* where n is from 1 to 99.

3. "&(i=n)" sets the stack pointer for stack ’i’ to n where 1 <= n <= 20.

4. "& ( i : <text> : ) " puts the text onto stack 'i'. (<text>

is a meta-symbol.)

Spaces are ignored in stack calls.

Stack pointer

An optional feature of types 1, 2, and 4 stack calls

are the two stack operators . "+” and which respectively

increment and decrement the stack pointer by 1 . As in the

language C, placement of the operators before or after the

stack identifier indicates whether the operation is performed before or after the stack is accessed. For example:

&(+e)

would first increment the stack pointer and then be replaced

by what is currently being pointed to in the stack ”e". The

stack operators should not be used on stack calls which appear in the pattern. If the stack operators are not used, a stack can be viewed as a simple variable.

- 15 -
The stack pointer is always initialized to point at position 1 and cannot be decremented below this position. If

the stack pointer points at position 1 and a decrement is

indicated, the stack pointer will continue to point at position 1. Before text is placed onto a stack position, that

position contains the null string.

- 16 -
6 . COUNTERS

M7 allows the user to have 26 general purpose counters

each of which has its own counter incremen t . The counters

are physically stored as integers, but they are used in the

pattern and the replacement definition in their character

string form. Conversion is done automatically. Bach

counter is identified by a lower case letter called the

counter identifier . These counters are useful for tasks

such as manipulating line numbers and counting bow many

times a pattern is matched. 4-rv

-Qojinter c.all constructions

There

all types

type 1 may

applicable

structions

are three basic counter call constructions. Vhile

may be used in the replacement definition, only

appear in the pattern and only types 2 and 3 are

to the counter command. The counter call conare :

1

1 • "#(i)" is replaced in

value of the counter

the string by

identified by "i".

the current

2. "#(i=n)" sets the counter to n where n integer greater than 0.

can be any

3. "#(i,n)" sets counter

a positive integer.

i's increment to n where n is

Spaces ignored in counter calls.

Counter increment

The two counter operators ^ ” and are similar to

the stack operators except that stack pointers are incremented or decremented by 1 whereas a counter is changed by

the value of its increment. These operators can be placed

before or after the counter identifier to indicate that the

counter should be incremented or decremented before or after

the particular function is performed. For example:

# (y+

)

would be replaced by the current value of the

after which the counter would be incremented.

counter .y.

Counters and increments are always initialized to 1 and

cannot be set to a value less than 1. As with stacks, the

operators should not be used in the pattern part of a macro.

- 17 -
£3C.amB 3l. ^. slL l£l££> Stacks . sJiA C.Qttn^fita.

For an example of how tags and stacks should be used, j consider the macro: i

* avg( { [0-9]* } , { [0-9]*) )

= / notice the

comment / * ( { 1 }+{2) )\/2 * &( 1

, a) &(2 ,b)

|

This would match the input:

avg(26,42)

and replace it with:

(26+i»2)/2

and then save the arguments "26" and "42" on stacks "a" and

"b", respectively. An example of the use of a counter would

be the macro:

•reset a' = ' done • # ( as 1 )

;

This would match the input:

reset a ‘

i and replace it with:

done

and set counter "a" to "1".

!

i

I

I

!

- 18 -
7. RESCAN FEATURE

M7 will repetitively match and rematch the text on an

input atrlng according to the macro definitions until no

more matches can be found. The algorithm for the matching

and replacement of input strings is as follows:

1 . 2 . 3.

4 .

5.

6 .

7.

Bead the next input string from the standard input.

If it is the end of the file then stop.

Get the first pattern.

Beplace all occurrenoes of the pattern in the

input with the replacement definition.

Did the current pattern occur in the input

at least once?

If yes, go to step 3*

Is there another pattern?

If yes, get the next pattern and go to

step 4.

Write out the new line and go to step 1

.

The "first pattern” refers to the most recent macro definition entered onto the macro file. Thus the first pattern

attempted to be matched would be taken from the last macro

definition in the macro file. The next pattern attempted to

be matched would be from the next to the last entry and so

on. Since the user can emit macros from other macros, as

discussed in section 8, these later generated macros will

always be scanned first.

The user should be careful not to cause M7 to go into

an infinite matching loop. A very simple example of this

would be the macro:

' int * = ' integer '

;

The pattern "int" would mate

it with "printeger". M7 w

tinuously march "int" and re

user should use the trace f

sure this type of replacemen

h the input "print" and replace

ill again use this macro to conplace it with "integer". The

eature (see section 9.0) to make

t does not occur.

The r« macro by u M7 w ill a

V the input

t ion . If s til the a

t ion can 0

escan feature can

sing "<" as the r texpt to change a string to what is

uccessful, the pa

ext input string

e used to avoid i

be turned off for

epl acement symbol

11 occurre nces of

fo und in the repl

t te rn will not be

is read in . Thus,

nfinite matching 1

a particular

instead of "=".

the pattern in

acement definiused again unthis construcoops

.

- 19 -
For example, the macro definition:

• ah' < ' abc *

;

and the input:

ababab

will result in:

abcabcabc

(end).

- 20 -
8. CONTROL COMMANDS

Any Input string which begins with the character "S" Is

considered a control command . The line will not be output

nor will an attempt be made to match any other patterns

against 1^. The legal commands and their uses are:

%MACRO - generates a new macro definition

](TRACE > enables/disables the trace (-t) option

IlNFLAG - enables/disables the print (-n) option

The format for the "^MACRO" command is:

JlMACRO *<macro deflnltlon>* ; This control command construction enables generation of

macros from other macros. The new macros are placed at the

end of the macro file, so that they will be scanned first.

For example, consider the macro:

*#deflne, { [a-z]*} , { [a-z]*} * = /

/ *%HkCH0 \*{1}\'=\M2)\*\; *1

The pattern of this macro would match the Input

"#def ine , cat , dog" and replace it with "%MACRO ’ cat ' = ' dog' ; "

.

The modified input string would be evaluated as a control

command structure and placed onto the preprocessed macro

file. The new macro would be the first macro to be scanned.

If the next input were "cat" it would be replaced by "dog".

Program flags can be set by typing:

5Kflagname> l(or 0)

where flagname can be "TRACE" or "NFLAG". The numbers 1 and

0 stand for ON and OFF respectively. For example, the input : %TRACE 1 will turn the trace option (the "t" option) on and the input : $NFLAG 1

will turn the n option on. These options are discussed

below. This construction can also be generated from a macro

as described above.

- 21 -
A command is not successful If an error occurs in the

macro of a macro generation command or if a symbol other

than *0* or *1* is the eighth character of the '^TRACE* or

*j(NFLAG' command. If an illegal macro is given, the same

error messages are displayed as when M7 is preprocessing the

input macro file; if an illegal value for a program flag is

given, an error message is displayed but execution does not

terminate.

- 22 -
9. EXECUTION OPTIONS

M7 has several calling options any one or all of which

may be specified using the standard UNIX calling procedure:

H7 C-p] [-t]

[-f ”<preprocessed file>" "<macro count>"]

[-a "<maoro definition>"] <maoro file>

The following is a list of the options and their functions.

1. The -t option will print a trace of the pattern

matching and replacement on the standard output.

This is very useful for "debugging" macro files. The

trace is of the form

oldline: <text before replacement>

macro #:n

newline : <text after replacement>

where n is the macro number, .(Numbers start with the

first entry in the preprocessed macro file.)

2. The -n option prints only the input strings which

were matched by at least one macro definition.

3. The -p option provides a prompt for initial input.

After M7 has preprocessed the macro file, "ready"

will be printed to inform the user that he can start

typing in input strings.

4. The -f option specifies a file which contains macros

that are already preprocessed. With this feature,

the user need not wait for M7 to repreprocess a commonly used macro file. The format for this option

is

-f "preprocessed file" "macro count"

where the prenrocessed file is the file of preprocessed macros and macro count is a count of the

number of macros in the file. A typical example

would be:

M7 -f "M7_WKS.tmp" "23"

The "f" option must be placed before any occurrence

of the "a" option and before the names of any files

which contain non-preprocessed macros. If the "f"

option is used, M7 will work with the specified file

-23
.

*' •

: r-ryl

instead of creating the new file ”M7_WKS . tmp" . The

user should refer to section 12 for information pertaining to the limitations of the 'f option.

5. The -a option Calces the following character string,

surrounded by. double quotes, as a macro definition.

This option may be repeated several times to put

several macros on the file. These macros will be the

first macros preprocessed and consequently will be

used after any macros in an unprocessed macro file.

6. More than one macro file may be specified in the argument list, ^he effect will be as though the files

were concatenated into a single file, with the macros in the latter files at the end.

- 24 -
10. USING M7

This section demonstrates a practical application of

M7. A systematic procedure for source translations using

pattern matching macros will be presented along with tips

and cautions on how to set up a macro file.

The first step in using M7 is to define what the input

and the output should look like. If the input and output

are well defined, fewer problems will be encountered while

writing the macros. Restrictions will usually have to be

put on the initial specifications because of implementation

limitations. The user should be aware of all the possible

combinations of input and be willing to change the specifications as necessary. The example below translates from a

FORTRAN-like DO statement to a C-llke ”for” statement.

FROM:

do <label> <index>=<init value> , <fInal value>,<inc>

<stmt1

>

<stmt2>

<stmtn>

<label> continue

TO:

for ( <index> = <init val> ; <indexX = <f inal value>;

<index>=<index>+<inc>){

<stmt 1 >

;

<stmt2>

;

<s tmtn>

}

A pictorial representation of this type is one way to

specify input and output. Another way is to set up a table

of possible inputs and the corresponding outputs. Do not

forget details. For example, the specifications of this example failed to show that the increment need not be specified in FORTRAN; it defaults to 1. Details such as these

should be included in the input and output specifications.

- 25 -
The next step would be to design a pattern matching al>

gorithB for the translation. This can be written out as a step by step word description of the pattern matching and

replaeeaent. For this example, the algorithm is:

1. Shrink the spacing (i.e. replace tabs and double

spacing with a single apace)

2. Match a FORTRAN "do” string and replace it with a C

programming language "for” string and store the label on a stack.

3. Hatch a statement which does not have a semicolon or

a brace at the end and replace it with a statement

with a semicolon at the end.

4. Natch the label stack at the beginning of a continue

statement and replace it with a right brace.

5. Strip off the label field.

The idea of shrinking spaces is an Important utility and is

used often.

The next step after the algorithm is written out is to

create a set of macros which will perform each step of the

algorithm. As they are written, each set should be tested

separately for correct output.

Precedence is important at this point. The ordering of

the macros in the macro file has a significant influence on

the output because of the rescanning algorithm. The macros

of higher precedence or ones that other macros depend on

should be placed closer to the end of the macro file so that

they are applied first. Space shrinking macros are usually

placed near the end of the macro file. The trace feature

can be used to see how the steps in the translation algorithm interact with each other. The following set of macros

perform the translation which was described previously:

1. ' step 3

2. ’do {?6«} {?2»}={?6«},{?6»}$'= step 2

’for({2}={3}\;{2}<={4}\;{2}++)\{’,&(1,a);

3. 'do {?6*} {?2«}=/ step 2

/{?6«},{?6«},{?6*}’ = ’for({2}={3}\; {2}<={4}\; {2}={2}+{5} )\{ ' ,&(1 ,a);

4

' "[ 0 - 91 *' =

' '

step 5

5. '‘“&(a) "continue' = '\}'; step 4

6. '* &(a) "continue' = '\}'; step 4

7. ' ’ =

'

' ; step 1 8. '\t' =

' '; step 1

- 26 -
The step numbers correspond to the step numbers of the word

description of the translation algorithm given above.

The first macro places the semicolon at the end of a statement. This macro is at the beginning of the file because it is the last macro to be matched. Otherwise, M7

would put a semicolon at the end of the "do” statement before translating it which is not what is desired. Note that

all semicolons which appear in the macro file which do not

terminate a maoro definition must be escaped.

The macros numbered 2 and 3 translate the FORTRAN "do”

statement into a C programming language "for” statement.

The ordering of these two macros in the macro file is significant. The third macro matches the optional increment

specification. The second macro will also match this structure. If the second macro were placed in front of the third

macro (i.e. further down in the file) the output would be

Incorrect.

The fourth macro removes numbers and spaces which occur

at the beginning of a line (i.e. removes the line numbers).

The patterns of the fifth and the sixth macros match

the end of the "do” loop (i.e. the label indicated on the

"do" statement, which was stored on a stack, is matched to

the beginning of a continue statement). Note, that this pattern is matched before the pattern of the macro that removes

the line numbers.

The seventh and eighth macros shrink the spacing; double spaces and tabs are replaced with single spaces. This is

done so that the patterns of macros 2 and 3 will match arbitrary spacing of the "do" statement.

The next step after the macros have been

checked for precedence is to test them on a input. Usually errors or limitations in the o rithm can be found at this step. For example,

this set of macros one would find that neste

would not work. This can be corrected by cha

ros so that the label indicated in the "do"

pushed onto the stack and then popped

corresponding "continue" statement is found.

written and

wide range of

riginal algoafter testing

d "do" loops

nging the macstatement is

off when the

Creating a set of macros to perform a desired translation is often as complex as writing a computer program; as

with a computer program the more time spent on the input and

output specifications and the matching algorithms the less

time spent on trial and error writing of macros.

- 27 -
Consider the matching process when using stacks or

counters. Macros should be written so their contents can be

dumped. For example:

'dump a* = *&(a)*;

would dump the contents of stack a. One should be careful

about pointing to the right position In a stack or using the

right value of a counter. Remember that the Increment and

the decrement operators have different meanings when placed

before or after a stack identifier.

It Is very easy to confuse M7. The user should check

the following things when problems occur:

1. that single quotes occur around the pattern and replacement definition.

2. that a semicolon occurs at the end of every 'macro

definition.

3. that special characters which are to be used as text

are escaped.

4. that semicolons which do not occur at the end of a macro definition are escaped.

A

- 28 -
11. FATAL ERROR MESSAGES

All errors detected by M7 (except Illegal values for

the t and n options) result In termination of execution.

This is done because execution after fatal errors is meaningless. The error messages that are generated are of the

form:

<routlne name> : <reason for termination>

The error occurred on macro # <macro number>

where the routine name is the name of the M7 subroutine

where the error was detected. (See the HI. Software Internals

Manual ) The error messages which occur during the preprocessing

of the macro file usually occur because of things like

missing quotes or unescaped special characters. The 'macro

file should be thoroughly checked when an error occurs in

preprocessing. The following is a list of the error messages which are generated during preprocessing and their

possible causes:

1

.

"M7 : cannot open pattern file" indicates

could not open the specified macro file,

should check the calling arguments used.

that M7

The user

2. "M7: cannot open ’f’ option file" indicates that M7

could not find the already existing preprocessed

macro file.

3. "M7

n f« the

Illegal placement o option was used a name of a user macro

f "f" option" indicates the

fter the "a" option or after

file was given.

4.

"PROCCALLS: error in macro definitions" indicates

that M7 reached the terminating character ’ ; ' before

it had finished processing the macro definition.

5.

"MAKPAT: pattern terminated early" indicates that M7

found the end of string character, EOS, in the pattern .

6. "MAKPAT: unbalanced tag braces" indicates M7 found

an unequal number of left and right braces in the

pattern

.

7. "MAKSUB: substitution text terminated early" indicates the end of string character, EOS, was found

before the terminating semicolon.

-29
8. "MAKSUB: preprocessed macro too large” Indicates a macro was entered which when preprocessed, expanded

beyond the 512 character limit.

9. "PROCCNTR: UNRECOGNIZEABLE CHAR" indicates that a

symbol other than *=* or was found in the

counter call. Thus, M7 could not recognize the type

of counter call it was.

10. "PROCSTCK: ILLEGAL CHARACTER” same as above except

for stacks. A symbol other than *=*, or *:* was

found.

11. "PROCCNTR: ILLEGAL USE OF *,*" and "PROCCNTR: ILLEGAL USE OF *s*” means that N7 found more than one of

the special symbols of a stack call and therefore

could not determine the type. Again, this is a syntax error.

12. "PROCSTCK: ILLEGAL USE OF *,*"» "PROCSTCK: ILLEGAL

USE OF '=*" and "PROCSTCK: ILLEGAL USE OF same

as above except for stacks.

13. "ESC: END OF STRING ENCOUNTERED TOO SOON" The end of

string character, EOS, was found before the delimiting quote or semicolon.

1M. "GETLINE: input string too long" indicates an input

string or an input macro was entered which was

longer than 1054 characters.

The error messages which occur after the preprocessing

of the macro definitions (i.e. after M7 prints "ready") usually occur because of internal confusion. This may be

caused by errors in the macro file which were not detected

during preprocessing. The following is a list of the error

messages which are generated after preprocessing.

1. "OMATCH: illegal pattern construction" indicates

that M7 expected to find one of the internally coded

commands but found gibberish instead. This usually

occurs when the user has an illegal construction

such as "•»" in the pattern.

2. "DOSTCK : error in

an invalid stack

stack call" indicates

call construction.

that M7 found

3. "DOCNTR : error in

found an invalid

counter call" indie

counter call construe

ates

t ion

that M7

-30
12. CONSTRAINTS AND LIMITATIONS

M7 has aone program limitations which may be changed in

future versions of H7. The following is a list of the known

limitations and constraints in M7

1. M7 does not indicate when it is in an indefinite

matching loop. If M7 does not seem to be responding

with any output, use the trace feature (see section

9*0) to see what is happening.

. -f "’v, 2. The use of stack and counter constructions, other

than type 1, can lead to peculiar results if placed

in the pattern. ' This is because M7 executes such

constructions as it is scanning the macro and the

input string. M7 actually makes several attempts to

match a pattern before being successful and with

each new attempt all the stack and counter calls are

executed again. If, during the course of trying to

match a pattern, M7 scans the pattern ten different

times, then the stack and counter calls in the pattern will be executed ten times. The stack and

counter calls placed before a macro’s pattern will

only be executed the first time M7 attempts to find

an occurrence of the pattern in a particular input

string while calls placed after a pattern will only

be executed if the pattern matches. This is why the

use of incrementation in a call within or before a pattern will almost certainly have disastrous

results. For this reason only type 1 stack and

counter calls should be used (and without any incrementation) in the pattern of a macro.

3. One possible reason for wanting to place such constructions in the pattern despite this warning would

be to use this powerful macro:

'{?2}&(1,a) &(a)*-’ < /delete reoccurrences/ '{1}';

This macro will tag alpha-numeric characters which

might be delimited by a space. The text that is

tagged is immediately placed on a stack so that other occurrences of the text in the same input string

may be deleted.

M. A preprocessed macro entry is restricted to 512

characters. This number can be changed by updating

the source code and recompiling the new version.

- 31 -
5. An input string or input macro is limited to 105M

characters which is the size of eight lines of

printer paper. This allows the user to put seven

lines of header on his macro file to improve the

looks of the file.

6. A stack entry is limited to 50 characters and each

stack has space allocated for 20 entries (i.e. the

stack pointer can legally be set to point at entries

at positions 1 to 20 on a stack). This can also be

changed by recompiling the source code.

7. Semicolons used for any reason other than terminating a macro definition must be escaped. This also

applies to double and single quotation marks which

do not delimit comments or sections of a macro.

8. File headers should be restricted to about 800 characters. If commentary text is too large a memory

fault will occur.

9. Care should be taken in using stacks and counters.

Although M7 checks for extraneous symbols , it does

not check for out of place letters, digits and plus

and minus characters

10. The 1 imit at ion on the number of macros with the • <*

feature has been set to 100 in this version of M7

However, the number can be changed by updating the

source code and then recompiling the entire program.

1

. The macros in the file given with

treated as though they all had "= ment symbol. If the user needs to

scan feature of any macros in h

through the preprocessing stage e cutes M7

the ’f’ option are

" as their replaceturn off the reis file, he must go

ach time he exe12. The name of

characters

the ’f option file is limited to ten

- 32 -
REFERENCES

BROW74 Brown, Peter J., Mafiro Processors and Technlaue^a: toj^ Portable

Software . London, New York, Wiley, 1974.

COLE76 Cole, Alfred John^' Macro Proceaaora . Cambridge, New York; Cambridge University Presm, 1976.

COOK73 Cook, A. James, "A User's Guide to CDC 7600/6600' HORTRAN ,

SLAC Computation Group, Stanford, California, 1973*

HALL71 Hall, Andrew 0.,j.^^he M6 Macro, Processor , ” Bell Telephone

Laboratories, Ino'i-$ Murray Hill, New Jersey, 1 9T1

.

KERN76 Kernlghan, Brian W» and P. J, Plauger, Software Tools . Addlson-Hesley Publishing Company, 1976.

SKIL80 Sklllman, G. H., et al., "The M7 Internals Manual," National

Bureau of Standards, Washington, D. C., In preparation.

WAIT70 Waite, W. M., "The Mobile Programming System: STAGE2",

Communications of the ACM, 13, 7, 415-421.
ttrlnK ot 1

wbl<tb

^

iirt,ar*r tb.4»

tJJJtl.lftl a^AAUJi ^ . '^ look* thk 'r'm . *

to./ t05k

t|^t if«#» of

S«i-'

west

•l^iio1b%fr#*!.Jt

,©xoo driJ03

Inf* Vi ‘

' y^. p ,, ,^

• 'f*“ ' a , e. fix a 3k«^iixi \x. ^ ‘i--

* I4

t,»f:i y

! '::3

"

fi]

'm#;, :aai,kif fl'f-'mftofpi

%u tnti''''’Vlt-'j^'M, if

s^lA.

VI

1 ,^

. ‘ bbib f#4'' b ft . »fM * $\ “^'' ' '

' • k#i-:- L r 0 9 j >.'n t i r• >fjB

-^1 : - M:r

Ilf"' ••»!•..... tA . tw'f ij(,«ff v,;-' it 'frlft ,f,41f

-#1^,

m

i-*k"

^ 'W JLi V *

.• 1' di Hv* '|;iiiS.'i#a tii«,

,!'i‘Jif /p..|

vi jik^il

" .--t! r

M

TJJ-;

•T ,*

•i„" '';*«
NBS«114A (REV. s-78)

U.S. DEPT. OF COMM.

BIBLIOGRAPHIC DATA

SHEET

1. PUBLICATION OR REPORT NO. NBSIR 80-2182

4. TITLE AND SUBTITLE

M7: A General Pattern Matching Facility Users Manual

5. Publication Date January 1981

7. AUTHOR(S)

A. R, Marriott, G. H. Skillman, S. B. Salazar, W. T. Hardgra

8. Performing Organ. Report No.

9. PERFORMING ORGANIZATION NAME AND ADDRESS

NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, DC 20234

11. Contract/Grant No.

12. SPONSORING ORGANIZATION NAME AND COMPLETE ADDRESS fSfreer, cuy. state, zip) 13. Type of Report & Perio(J Covered

15. SUPPLEMENTARY NOTES

fu^ocument describes a computer program; SF-185, FIPS Software Summary, is attached.

16. ABSTRACT (A 200-word or leas tactual aummary ot moat aignilieant inlormation. If document includes a significant bibliography or

literature survey, mention it here.) M7 is a general pattern matching and replacement facility. It is based on such macroprocessors as M6, MORTRAN, and STAGE 2, and has been implemented in the

language C on UNIX. By incorporating such features as stacks, counters, and tags,

M7 is particularly useful for translating or reformatting queries, languages

and data.

17. KEY WORDS (six to twelve entries; alphabetical order; capitalize only the first letter of the first key word unless a proper name;

separated by aemicotons)

Macroprocessor; pattern matching; query processor; software tool; text processor;

translation; UNIX.

18. AVAILABILITY mUnlimited

I I For Official Distribution. Do Hot Release to NTIS

I I Order From Sup. of Doc., U.S. Government Printing Office, Washington, DC

20402, SD Stock No. SN003-003-

[X~l Order From National Technical Information Service (NTIS), Springfield, VA. 22161

19. SECURITY CLASS

(THIS REPORT)

UNCLASSIFIED

20. SECURITY CLASS

(THIS PAGE)

UNCLASSIFIED

21. NO. OF

PRINTED PAGES

38

22. Price

$ 6.00

USCOMM-DC
^ oti to ^v|».

w «iw«.<*.i«tq.cr^toi [*—“

v-»»Ud«i vRt^a^ »<> tfimUoxtoQ »k 

m;

g^., ,if/— :i- ; _ ^