程序代写代做代考 compiler Assignment 2 — Feature grammars

Assignment 2 — Feature grammars

Assignment 2 — Feature grammars

CSC485/2501 – Fall 2018

1

Slides are based on ALE user’s guide by Carpenter & Penn
http://www.ale.cs.toronto.edu/docs/man/ale_trale_manual.pdf

Nona Naderi

http://www.ale.cs.toronto.edu/docs/man/ale_trale_manual.pdf

Running TRALE

• Use tcsh.
• Remove the default virtual memory limit:
limit vmemoryuse unlimited

• Starting TRALE (ssh with the -X flag):
path to trale/trale -fsg

2

Getting started (1)

• Load a grammar:
?- compile gram(grammar).

• Check lexical entries:
?- lex(puppies).

• Check rules:
?- rule(srule).

• Executing a grammar – input for parsing:
?- rec[john,walks].
Note:

• Input string as a list.
• No variables in the query.

3

Getting started (2)

• If there are no parses, ’no’ is returned:
?- rec[walks,john].

STRING:

0 walks 1 john 2

no

• Other lexical entries, rules, parses:
ANOTHER? y.

• The fullstop is necessary with all commands.

4

Types

• Every feature structure has a type.
• Types have subtypes (more specific instances of the type).
• Type names must be lower-cased.
• The most general type is bot.
• Everything is a sub-type of bot.
• A simple type specification: the name of the type, followed by

the keyword sub, followed by a list of its subtypes, e.g.,

bot sub [b,c].

b sub [d,e].

d sub [].

e sub [].

c sub [].

5

Feature structure

• A collection of feature/value pairs.
• E.g., type vp (with no subtypes) has a feature subj with value
np:

vp sub []

intro [subj:np].

6

Type system

• Appropriateness: each type must specify:
• which features it can be defined for,
• which type of values such features can take.

7

Lexicon

• Adding lexicon:
john −−−> np.
walked −−−> vp.

8

Grammar rules
• Name of the rule: srule.
• Atom rule specifies type of info for ALE compiler.
• Nonterminal of the mother: s (nonterminals are lower-cased).
• Daughter categories indicated by cat>.
• Order is important.
• Add comments (using ’%’) to explain what your grammar

does.

% Grammmar Rule allowing the combination of

% np category with a vp type category

srule rule

s

===>

cat > np ,

cat > vp.
9

Simple grammar

% Type Hierarchy

bot sub [s,np,vp]. % Three sub-types of bot

s sub []. % Each with no sub-types

np sub [].

vp sub [].

% Lexical Entries

john −−−> np.
walked −−−> vp.
% Grammmar Rules

srule rule

s

===>
cat> np,
cat> vp.

10

Simple grammar

bot sub [pp,p,np].

pp sub [].

p sub [].

np sub [].

with −−−> p.
sam −−−> np.
srule rule

pp

===>
cat> p,
cat> np.

11

Variables

• Start with upper-case letters.
• Variables with the same name must unify.

cat sub [s,np,vp].

np sub []

intro [index:index ].

vp sub []

intro [subj:np].

s sub [].

srule rule

s

===>

cat > (np ,index:Ind),

cat > (vp ,subj:index:Ind).

12

INDEX feature

• Takes the type index as its value.
• Contains agreement features, gender, number, and person.

index sub []

intro [p:person ,num:number ,g:gend].

person sub [first ,second ,third ].

number sub [sing ,plural ].

gend sub [m,f,n].

13

Exercise (1)

• Modify this grammar in a way that parses I walk.
bot sub [s,np,vp].

s sub [].

np sub [].

vp sub [].

john −−−> np.
walks −−−> vp.
srule rule

s

===>
cat> np,
cat> vp.

• Does it parse I walks? or John walk? How can you avoid it?

14

Exercise (2)

• Modify the previous grammar in a way that parses John walks
with Sam.

15