Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[da_nang]

I actually think think the might, but I'm not sure.

I don't think so.

Let α, β and γ be regular expressions. Can α(?=β)γ be transformed to a regular expression without lookahead? Note, I'm assuming the parser doesn't do substring matching i.e. the whole string must satisfy the regular expression since I think it would otherwise be possible to parse context-free languages. In other words, ^ and $ are applied.

First off, what does "lookahead" mean? AFAIK, it simply says if the parser can match a string satisfying β after α, then it will proceed "without consuming" the match. To me, that says that in order for the whole input string to be accepted, the regular expression β must exist within γ. Therefore it follows that γ = δβζ, where δ and ζ are regular expressions, which may be the empty string.

Assuming that γ = δβζ such that δ and ζ are known, then one can easily construct an NFA-ε that is equivalent to the regular expression and therefore represents regular languages.

For α(?!β)γ, the negative lookahead says that β should not occur after α. Therefore, γ = δηζ where η is the negation of β. The other regular expressions remain the same but also don't contain β. Hence the regular expression is now αδηζ and should be convertible to an NFA-ε.

The same method should work for lookbehind as well, only that you apply it to α instead of γ.

[Mego]

And regular expressions are awesome. Hell, I use them all the time just for the games I run on the forum or when writing scripts. They are incredibly for any sort of "find/replace" need, since they support backreferences.

Deep inside me, a formal language theory student cries.

Wait, what do formal language theory students have against capture groups? I've... don't think I've seen a regex implementation that *doesn't* support them in quite a while...

Next you'll be saying lookaheads and lookbehinds and recursive patterns make you cringe in pain or something!

Simply put, there are two definitions of regular expressions. The first and classic one is based entirely on Kleene algebra and supports union '+' (sometimes '|'), concatenation '·' and Kleene star '*'. This definition is equivalent to a DFA and thus represents regular languages (and in turn finite languages). This is what they teach you in Formal Language Theory.

The second one is based on either POSIX Extended Regular Expressions or Perl Regular Expressions (I forget which) that supports backreferences. Backreferences essentially add "memory" to the parser, something which DFAs do not support. In fact, it can be proven by the pumping lemma that the addition of backreferences leads to the parser being able to parse more than just regular languages (such as palindromes).

Calling them regular expressions to someone who is more familiar with the former definition sounds more like a misnomer, hence the cringe.

Lookaheads and lookbehinds, on the other hand, don't change what languages can be parsed AFAIK.

Spoiler: HEY GUYS LET'S GO OVER FORMAL LANGUAGE TYPES! (click to show/hide)

Languages are sets of strings of symbols with syntax rules which dictate what is legal and what isn't. Grammars define those rules.

First, you've got your generic grammar, represented by a 4-tuple: (N,V,P,S). N is your (finite) set of nonterminal symbols, V is your (finite) set of terminal symbols, P is your set of productions, and S is the start symbol.

A nonterminal symbol is one which can, through a production in P, be (eventually) evaluated into one or more terminal symbols. A terminal symbol is one which cannot be evaluated any further. S is the symbol at which you must begin producing from, and is usually a nonterminal. S must be a member of N or V.

Productions are the important thing. They look like this: A -> B. A is some combination of symbols containing at least one nonterminal, and B is another combination of symbols (that can contain any number of terminals and nonterminals, unlike A). Basically, they tell you what evaluations are legal to perform.

An example would be:

N = {A,B,S}
V = {a,b}
S = S
P = { S -> A,
        S -> AB,
        A -> aA,
        A -> a,
        B -> bB,
        B -> b }

This is a very simple grammar, and as such is easy to describe the language it produces. The language consists of all strings with containing one or more a's, followed by zero or more b's. In POSIX regex syntax, it would be a+b*.

There exists a convention called the erasing convention, which is:
1. If a production exists in P where the empty string (denoted λ) can be produced, it must be S -> λ (called the erasing production).
2. If the erasing production is in P, S may not appear on the right side of any other productions.

This means that you can only generate an empty string from the beginning of a production sequence. It's important because, otherwise, potentially any production sequence could result in an empty string.

In 1956, a lunatic named Noam Chomsky created a hierarchy of these formal grammars, called the Chomsky hierarchy. The levels are:

Type 0 (recursively enumerable): Any formal grammar

Type 1 (context-sensitive): The grammar must follow the erasing convention, and all productions must be of the form A -> B, where |A| (the length of A) >= |B|, with the exception of the erasing production.

Type 2 (context-free): As Type 1, and all productions must have only a single nonterminal symbol on the left-hand side. Most programming languages' statements are type 2 (mostly - scope resolution and declarations are typically type 1).

Type 3 (regular): As Type 2, and all productions must be of the form A -> t or A -> tW, where t is a single terminal symbol and W is a single nonterminal symbol. The original, strict definition of regular expressions (which da_nang described) recognize these languages.

[Skyrunner]

C++'s implementation of templates has a gotcha I dislike. You can't do the traditional declaration-in-header, definition-in-cpp file structure. You have to either put the whole thing into the header, or make a, say, tpp file that has the definitions of only the templated functions and #include them right after the declarations. At least that way you can keep the header files simple, but it effectively pastes the file content into the header

Oh, one more way is explicitly declaring what templated types of that function you want to use.

[da_nang]

And regular expressions are awesome. Hell, I use them all the time just for the games I run on the forum or when writing scripts. They are incredibly for any sort of "find/replace" need, since they support backreferences.

Deep inside me, a formal language theory student cries.

Wait, what do formal language theory students have against capture groups? I've... don't think I've seen a regex implementation that *doesn't* support them in quite a while...

Next you'll be saying lookaheads and lookbehinds and recursive patterns make you cringe in pain or something!

Simply put, there are two definitions of regular expressions. The first and classic one is based entirely on Kleene algebra and supports union '+' (sometimes '|'), concatenation '·' and Kleene star '*'. This definition is equivalent to a DFA and thus represents regular languages (and in turn finite languages). This is what they teach you in Formal Language Theory.

The second one is based on either POSIX Extended Regular Expressions or Perl Regular Expressions (I forget which) that supports backreferences. Backreferences essentially add "memory" to the parser, something which DFAs do not support. In fact, it can be proven by the pumping lemma that the addition of backreferences leads to the parser being able to parse more than just regular languages (such as palindromes).

Calling them regular expressions to someone who is more familiar with the former definition sounds more like a misnomer, hence the cringe.

Lookaheads and lookbehinds, on the other hand, don't change what languages can be parsed AFAIK.

Spoiler: HEY GUYS LET'S GO OVER FORMAL LANGUAGE TYPES! (click to show/hide)

Languages are sets of strings of symbols with syntax rules which dictate what is legal and what isn't. Grammars define those rules.

First, you've got your generic grammar, represented by a 4-tuple: (N,V,P,S). N is your (finite) set of nonterminal symbols, V is your (finite) set of terminal symbols, P is your set of productions, and S is the start symbol.

A nonterminal symbol is one which can, through a production in P, be (eventually) evaluated into one or more terminal symbols. A terminal symbol is one which cannot be evaluated any further. S is the symbol at which you must begin producing from, and is usually a nonterminal. S must be a member of N or V.

Productions are the important thing. They look like this: A -> B. A is some combination of symbols containing at least one nonterminal, and B is another combination of symbols (that can contain any number of terminals and nonterminals, unlike A). Basically, they tell you what evaluations are legal to perform.

An example would be:

N = {A,B,S}
V = {a,b}
S = S
P = { S -> A,
        S -> AB,
        A -> aA,
        A -> a,
        B -> bB,
        B -> b }

This is a very simple grammar, and as such is easy to describe the language it produces. The language consists of all strings with containing one or more a's, followed by zero or more b's. In POSIX regex syntax, it would be a+b*.

There exists a convention called the erasing convention, which is:
1. If a production exists in P where the empty string (denoted λ) can be produced, it must be S -> λ (called the erasing production).
2. If the erasing production is in P, S may not appear on the right side of any other productions.

This means that you can only generate an empty string from the beginning of a production sequence. It's important because, otherwise, potentially any production sequence could result in an empty string.

In 1956, a lunatic named Noam Chomsky created a hierarchy of these formal grammars, called the Chomsky hierarchy. The levels are:

Type 0 (recursively enumerable): Any formal grammar

Type 1 (context-sensitive): The grammar must follow the erasing convention, and all productions must be of the form A -> B, where |A| (the length of A) >= |B|, with the exception of the erasing production.

Type 2 (context-free): As Type 1, and all productions must have only a single nonterminal symbol on the left-hand side. Most programming languages' statements are type 2 (mostly - scope resolution and declarations are typically type 1).

Type 3 (regular): As Type 2, and all productions must be of the form A -> t or A -> tW, where t is a single terminal symbol and W is a single nonterminal symbol. The original, strict definition of regular expressions (which da_nang described) recognize these languages.

There's technically one set of languages "above" type 0, though. The hierarchy is more specifically:

All formal languages (uncountably infinite set, yay!)
Recursively enumerable languages (Languages that can be computed/parsed on a Turing machine)
Recursive languages (Languages that can be computed/parsed on a total Turing machine)
Context-sensitive languages
Context-free languages (Virtually all syntax grammars in programming languages, can be parsed on a pushdown automaton)
Regular languages (Pattern matching, yay! Can be parsed by DFA)
Finite languages (The "boring" set)

[MorleyDev]

I made a gaem for my coursework for university Wrote it using Scala and JSFML in like 3 days whilst dealing with the pain and the painkillers from wisdom tooth infection xD Well, I wrote some of the background code about a week ago (the basic client/server and Game "launch/run/close" framework), but the actual "game" part of it was written in 3 days.

Spoiler (click to show/hide)

Spoiler (click to show/hide)

It's just a rapidly developed prototype and it's basically a poorly coded pacman (by my standards at least). But it's not just a poorly coded pacman, it's a multiplayer pacman played over a network where one player is pac and up to 3 players control the ghosts.

Ghosts have limited field of view, so can only see tiles close to them, but they do also share sight with the other ghosts. So they have to work together to find and kill the Pacman.

I didn't get a chance to play around with Akka or Actors so all the networking uses Java sockets over TCP. Not ideal, but it serves it's purpose I guess.

Not bad for 3 days of delirious work. Exploitable as hell, ghosts can make it impossible for the pac player to win by just staying still since I didn't get around to implementing the power pellet before calling it a day and handing it in. But as far as "proof of concept prototype" I guess it works

But on a whole, developing games in Scala? Surprisingly pleasant. Scala is rapidly becoming my go-to language.

Oh, source code can be found at github. It uses sbt for compiling, so "sbt universal:package-bin" will create a zip archive containing the launch scripts, resources and jar files.

[DrKillPatient]

Hi. Quick regex question; I found this in Ruby's documentation:

Code: [Select]

[a-w&&[^c-g]z]
Why does this regex exclude 'z'? My understanding is that it reads "Anything from 'a' to 'w' that is NOT anything from 'c' to 'g' or that is 'z', but it seems I'm not right about the last part.

[gigaraptor487]

Thats awesome morleydev! I may have a look through some the games I have written and take screenshots

[Maklak]

See if this works then: [abh-wz]

[DrKillPatient]

See if this works then: [abh-wz]

Well, I know that that particular regex does what I described — what I'm wondering is why the one I mentioned doesn't do the same thing. I'm curious about what the syntax there means, really.

[Levi]

Hi. Quick regex question; I found this in Ruby's documentation:

Code: [Select]

[a-w&&[^c-g]z]
Why does this regex exclude 'z'? My understanding is that it reads "Anything from 'a' to 'w' that is NOT anything from 'c' to 'g' or that is 'z', but it seems I'm not right about the last part.

BTW, here is a handy website for figuring out ruby regexps:  http://rubular.com/


It sounds like the && is an intersect operator(never used it in a regex myself).  So the regular expression is kind of like:

a-w AND (not(c-g) or z).

z doesn't intersect with a-w, so its excluded.  Its essentially means

Code: [Select]

[a-w&&[^c-g]z] is the same as

Code: [Select]

[a-w&&[^c-g]] which is the same as

Code: [Select]

[a-w&&[a-b][h-z]] which is the same as

Code: [Select]

[a-b[h-w]]

[Angle]

Alright, so I've got my Perplexicon RL game, right? Right now I'm trying to program items to take damage. The problem here is that I have a variety of effects that can happen from damage, and I want to keep open the possibility of modding in more. I'm thinking of having the attack have a list of damage types- Electric, peircing, peicing+, impaling, crushing, burning, etc. then I'll have a soft-coded list of scripts, one for each type of damage, that calculate the effects of that damage. So if you decide to add void damage, or sonic damage, or whatever, you can simply modify the item information and add a script for it. This is fairly complicated, but it's possible, and even if difficult at least I'll be doing something instead of sitting here failing to make any kind of decision. I'll be soft-coding the scripts in groovy, and using one of these techniques to import them into java. Can anyone think of a better way to do things?

[MagmaMcFry]

I don't think you need that many types of damage at all. Give items a single HP value, and give them three damage multipliers: against blunt damage (crushing, sonic, void, impact), pierce damage (piercing, impaling, cutting) and heat damage (electric, burning). All other damage types are usually close to one of those three.

[Kassire]

Am I an idiot? I've been working with the unity3d 2d tools (Sample assets) and for some reason the box collider 2d won't work as I'm trying to have the player be on the ground and the player is just clipping through the ground. 

[alexandertnt]

Am I an idiot? I've been working with the unity3d 2d tools (Sample assets) and for some reason the box collider 2d won't work as I'm trying to have the player be on the ground and the player is just clipping through the ground.

Some things to try:

• Are the player and the ground on the same layer?
• Are either colliders marked as a trigger (triggers won't physically collide with anything)
• Are you accidently mixing 2d and 3d colliders/rigidbodies
• Is everything scaled properly? i.e. no microscopic player and floors. (compare it to a default cube, which is 1m x 1m x 1m)

[Lightningfalcon]

I have a question.  I have an RSA program where I can specify the size of two different prime numbers.  How do I calculate the size of the number they form when multiplied?